Binary Trees

For more on BinaryTree check out Trees.

Invert Binary Tree - Easy

This is a CLASSIC example of a problem that demonstrates Recursion and BinaryTree understanding.

1. As always start by defining your base-case which is the empty node (or tree).
2. Then swap the left and right using a temporary node for one of them.
3. Then recursively call the function on the right and left branches.
4. Return the tree at the end. My Java implementation (it’s FAST)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
 
        if(root == null){
            return root;
        }
 
        TreeNode tempNode = root.right;
        root.right = root.left;
        root.left = tempNode;
 
        invertTree(root.right);
        invertTree(root.left);
        
        return root;
        
    }
}

This solution has a time complexity of $O(n)$ where $n$ is the number of nodes in the tree and $O(h)$ space complexity where $h$ is the number of levels or the height of the tree.

Find Lowest Common Ancestor of BST - Easy

The Lowest Common Ancestor (LCA) refers to the lowest (by height not value) node in the tree that’s a common ancestor. You’re given a tree and two nodes p and q, and you need to find their LCA. ==Sometimes the root is the lowest, or either p or q in some edge cases.==

Since this is a BST, we’re going to loop through level by level, making a decision to go left or right. When we encounter a split, with p value less than current value and q value greater, then by definition of BST that’s the LCA. Code:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
	TreeNode current = root;
	while(current != null){
		if(p.val < current.val && q.val < current.val){
			current = current.left;
		}
		else if(current.val < p.val && current.val < q.val){
			current = current.right;
		}
		else{
			// encounter a split, i,e found LCA
			return current;
		}
	}
	return root;
    }

Balanced Binary Tree - Easy

A Binary Tree in which the depth of the two subtrees of every node never differs by more than one.

Breakdown

1. Get the height of the left and right sub-trees. Use recursion to get the height, base case is null of course.
2. Get the absolute height difference
3. Check if abs diff is less than or equal to one.

Balanced binary tree

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Naive Top-Down recursive approach

This one involves traversing from the root recursively towards the bottom of the binary tree to get the heights. Code:

class Solution {
    int height(TreeNode root) {
        if (root == null) {
            return 0;
        }        
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight > rightHeight) {
            return 1 + leftHeight;
        }
        else {
            return 1 + rightHeight;
        }
        // can do instead: return 1 + Math.max(height(root.left), height(root.right));
	}
 
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
 
       int left = height(root.left);
       int right = height(root.right);
        if (1 < Math.abs(right - left)){
            return false;
        } 
        
        return isBalanced(root.left) && isBalanced(root.right);
    }
}

Because we’re traversing recursively through twice, once when we get the height and then when we compare if EVERY sub-tree is balanced) this ends up being $O(n^2)$ and space complexity of $O(h)$.

Better Bottom-Up recursive approach

Instead of doing the recursive traversal twice, in two functions. Instead, we make two calls per sub-tree in one function, and based on their difference return a boolean then and there. As explained in this Digital Ocean article. Algorithm:

• If node == null → return 0
• Check left subtree. If not balanced → return -1
• Check right subtree. If not balanced → return -1
• The absolute between heights of left and right subtrees. If it is greater than 1 → return -1.
• Else, return the 1 + max height between the left and right subtree
• Check if the result is greater than 0.

Code:

class Solution {
    public int helper(TreeNode root){
          if(root == null){
            return 0;
        }
        int left = helper(root.left);
        int right = helper(root.right);
 
        if(left == -1 || right == -1 || (1 < Math.abs(right - left))){
            return -1;
        }else{
            return 1 + Math.max(left, right);
        }
    }
 
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        return 0 < helper(root);
    }
}

This is much faster, because we’re only traversing recursively twice per node in a single function. Time complexity of $O(n)$ and space complexity (i think) is the same $O(h)$.