Published on: 05/07/2024

Leetcode #110 : Balanced Binary Tree

Approach 1: Top-down recursion

Algorithm

First we define a function height such that for any node p \in T
height(p) =
-1 p is an empty subtree i.e. null
1 + max(height(p.left), height(p.right)) otherwise

Now that we have a method for determining the height of a tree, all that remains is to compare the height of every node’s children. A tree T rooted at r is balanced if and only if the height of its two children are within 1 of each other and the subtrees at each child are also balanced. Therefore, we can compare the two child subtrees’ heights then recurse on each one.

Implementation

class Solution{
  // Recursively obtain the height of a tree. An empty tree has -1 height
  private int height(TreeNode root){
    // An empty tree has height -1
    if(root == null)
      return -1;

    return 1 + Math.max(height(root.left), height(root.right));
  }

  public boolean isBalanced(TreeNode root){
    // An empty tree satisfies the definition of a balanced tree
    if(root == null)
      return true;

    // Check if subtrees have height within 1. If they do, check if the 
    // subtrees are balanced
    return (
      Math.abs(height(root.left) - height(root.right) < 2 &&
      isBalanced(root.left) &&
      isBalanced(root.right)
    );
  }

}

Approach 2: Bottom-up recursion

Intuition

In approach 1, we perform redundant calculations when computing height. In each call to height, we require that the subtree’s heights also be computed. Therefore, when working top down we will compute the height of a subtree once for every parent. We can remove the redundancy by firs recursion on the children of the current node and then using their computed height to determine whether the current node is balanced.

Algorithm

We will use the same height defined in the first approach. The bottom-up approach is a reverse of the logic of the top-down approach since we first check if the child subtrees are balanced before comparing their heights. The algorithm is as follows:

Implementation

class Solution {

  public boolean isBalanced(TreeNode root){
    if(dfs(root) == -1)
      return false;
    return true;
  }

  private int dfs(TreeNode root){
    // Base case
    if(root == null)
      return 0;
    int left = dfs(root.left);
    int right = dfs(root.right);

    if(Math.abs(left - right) > 1 || left == -1 || right == -1)
      return -1;
    return Math.max(left, right) + 1;
  }
}

Leetcode #543 : Diameter of Binary Tree

Aglorithm

• Initalize an integer variable diameter to keep track of the longest path we find from DFS.

• Implement a recursive function longestPath which takes a TreeNode as input. It should recursively explore the entire tree rooted at the given node. Once it’s finished, it should return the longest path out of its left & right branches:

  • If node is None, we have reached the end of the tree, hence we should return 0;
  • We want to recursively explore node’s children, so we call longestPath again with node’s left & right children. In return, we get the longest path of its left & right children leftPath & rightPath;
  • If leftPath plus rightPath is longer than the current longest diameter found, then we can update diameter;
  • Finally, if we return the longer one of leftPath and rightPath. Remember to add 1 as the edge connecting it with its parent.

• Call longestPath with root.

class Solution {

  private int diameter;
  public int diameterOfBinaryTree(TreeNode root){
    diameter = 0;
    longestPath(root);
    return diameter;
  }

  private int longestPath(TreeNode node){
    if(node == null) return 0;
    // Recursively find the longest path in
    // left & right child
    int leftPath = longestPath(node.left);
    int rightPath = longestPath(node.right);
    
    // Update the diameter if leftPath + rightPath is larger
    diameter = (leftPath + rightPath > diameter) ? leftPath + rightPath : diameter;

    // Return the longest one between leftPath & rightPath;
    // remember to add 1 for the path connecting the node and its parent
    return Math.max(leftPath, rightPath) + 1;
  }
}

Leetcode #733 : Flood Fill

Approach: Depth-First Search

Intuition

We perform the algorithm explained in the problem description: paint the starting pixels, plus adjacent pixels of the same color, and so on.

Aglorithm

Say color is the color of the starting pixel. Let’s flood fill the starting pixel: we change the color of the pixel of the new color, then check the 4 neighboring pixels to make sure they are valid pixels of the same color, and of the valid ones, we flood fill those, and so on.

We can use a function dfs to perform a flood fill on a target pixel

class Solution {
  public int[][] floodFill(int[][] image, int sr, int sc, int newColo) {
    int color = image[sr][sc];
    if (color != newColor) {
      dfs(image, sr, sc, color, newColor);
    return image;

    }
    public void dfs(int[][] image, int r, int c, int color, int newColro){
      if (image[r][c] == color){
        image[r][c] = newColor;
        if (r >= 1)
          dfs(image, r - 1, c, color, newColor);
        if (c >= 1)
          dfs(image, r, c - 1, color, newColor);
        if (r + 1 < image.length)
          dfs(image, r + 1, c, color, newColor);
        if (c + 1 < image[0].length)
          dfs(image, r, c + 1, color, newColor);
      }
    }
  }
}

---

Tree Definition

First of all, here is the definition of a TreeNode which we would use.

// Definition for a binary tree node.
public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode(int x) {
    val = x;
  }
}

Intuition

On the first sight, the problem is trivial. Let’s reverse the tree and check at each step if node.right.val > node.val and node.left.val < node.val. This approach would even work for some trees.

The problem is this approach will not work for all cass, Not only the right child should be larger than the current node but all the elements in the right subtree. Here is an example:

This means one should keep both upper and lower limits for each now whilte traversing the tree, and compare the node value not with children values, but with these limits.

---

Approach 1: Recursive Traversal with Valid Range

The idea above could be implemented as a recursion. One comprares the novde value with its upper and lower limits if they are available. The one repeats the saem step recursively for left and right subtrees.

class Solution{
  public boolean isValidBST(TreeNode root){
    return dfs(root, Long.MAX_VALUE, Long.MIN_VALUE);
  }
  public boolean dfs(TreeNode root, long upperLimit, long lowerLimit){
    if (root == null)
        return true;
    else if (root.val <= lowerLimit || root.val >= upperLimit)
        return false;
    boolean l = dfs(root.left, root.val, lowerLimit);
    boolean r = dfs(root.right, upperLimit, root.val);
    return (l && r);
  }


}

Complexity Analysis

* Time complexity: O(N) — Since we visit each node exactly once.

* Space complexity: O(N) — Since we keep up to the entire tree.

---

---