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.

Maximum Depth of Binary Tree

Find the max depth i,e, height.

maxDepth(root) {
	if (root === null){
		return 0;
	}
	
	let left = 1 + this.maxDepth(root.left);
	let right = 1 + this.maxDepth(root.right);
	
	return Math.max(left, right);
}

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.

Algorithm breakdown:

• If root is null or equals the value of either p or q then it’s the LCA
• If values of p and q are less than root’s, then search left subtree
• If values of p and q are greater than root’s, then search right subtree
• Otherwise you’ve found the split, meaning the node is the LCA

Code:

def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
 
	if not root or root.val == p.val or root.val == q.val:
		return root
 
	if p.val < root.val and q.val < root.val:
		return self.lowestCommonAncestor(root.left, p, q)
	elif root.val < p.val and root.val < q.val:
		return self.lowestCommonAncestor(root.right, p, q)
	else:
		return root

Lowest Common Ancestor of Binary Tree (Not BST) - Medium

This one’s a doozy because I find the LCA definition to be confusing.
The LCA is the lowest node (closest to root) that has both p and q in its subtree.

Obviosly this can be solved using dfs or bfs but the sauce is in the base cases

Note, that this problem isn’t concerned with the values of the nodes. Since it’s not a binarysearchtree , it can duplicate values! // Check for Node references not node values

DFS Algorithm

• Base cases: if root is null or root itself is either p or q, then return root
• Recursive call to root’s left subtree followed by a recursive call to its right subtree
• Check if both subtrees are not null, return root
• Otherwise return the one that’s not null

Code:

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
	if not root or root == p or root == q:
		return root
	left = self.lowestCommonAncestor(root.left, p, q)
	right = self.lowestCommonAncestor(root.right, p, q)
 
	if left and right:
		return root 
	
	return right if right else left

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)$.

Same Tree

DFS

def is_same_tree(p, q):
	if not p and not q:
		return true
	elif p and q and p.val == q.val:
		return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)
	else:
		return False

BFS

The scanning of neighbours using the for-loop wasn’t intuitive

def isSameTree(p,q):
	fst = deque()
	fst.append(p)
	sec = deque()
	sec.append(q)
	
	while fst and sec
		# checks all the neighbours per level
		for i in range(len(fst)):
			i = fst.popleft()
			j = sec.popleft()
			# visit and check
			if not i and not j: 
				continue # nothing to return but need to check...
			if not i or not j or i.val != j.val: return False
			
			fst.append(i.left)
			sec.append(j.left)
			fst.append(i.right)
			sec.append(j.right)
	return True

Level Order Traversal - Medium

This is the standard Binary Tree LOT problem.
Given a Binary Tree, return an array of arrays, with each containing the values of the nodes on that level.

For an algorithm breakdown, read Graph and Tree Algorithms > Level Order Traversal.
The only thing to consider is to loop through the level using the size of the queue as the number of nodes per level.

Code:

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
	if not root:
		return []
 
	Q = deque()
	Q.append(root)
	order = []
	while Q:
		lvl_size = len(Q)
		lvl = []
		for i in range(lvl_size):
			cur = Q.popleft()
			if cur:
				lvl.append(cur.val)
				if cur.left: Q.append(cur.left)
				if cur.right: Q.append(cur.right)
		order.append(lvl)
	
	return order