(Minimum Depth of Binary Tree)

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Thoughts:
Sense of recursion should be came out now.
What is the base case or edge case? Empty tree. What is the minimum depth of an empty tree? 0.
In the recursion step, the passed in TreeNode “root” is been looked at. “root” is not null, which was covered in the base case. Then there are four sub-cases or combinations, if you like:

  1. root is a leaf node. In other word, root.left == null && root.right == null. Return 1 at this case.
  2. root.left == null && root.right != null. Then we just need to recurse on the right, so we return 1 + minDepth(root.right).
  3. root.left != null && root.right == null. Similarly, we return 1 + minDepth(root.left).
  4. root.left != null && root.right != null. This is rather interesting case. We don’t know which branch of the case has shorter path, so we should return the minimum of these two.

In the code, we can actually combine the four cases into two!

Code (Java):

public class Solution {
    public int minDepth(TreeNode root) {
        if(root == null)
            return 0;
        else {
            if(root.left != null && root.right != null)    
                return 1 + Math.min(minDepth(root.left), minDepth(root.right));
            else
                return 1 + minDepth(root.right) + minDepth(root.left);
        }
            
    }
}

Code (C++):

class Solution {
public:
    int minDepth(TreeNode *root) {
        if(root == NULL)
            return 0;
        else if(root -> left != NULL && root -> right != NULL)
            return 1 + min(minDepth(root -> left), minDepth(root -> right));
        else
            return 1 + minDepth(root -> right) + minDepth(root -> left);
    }
};
Advertisements

Print all paths in a binary tree which sum up to a value

You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree – it does not have to start at the root.

My initial thoughts:
Two recursive structures:

  1. Recursively traverse every node in the tree.
  2. Rooted at a single node r with value r.value(), recursively find paths that contains value – r.value().

My initial codes:

	public static void printAllPathsSumUpTo(BinaryTreeNode<Integer> root,
			int value) {
		printRecursively(root, value, new String());
		if (root != null) {
			printAllPathsSumUpTo(root.getLeft(), value);
			printAllPathsSumUpTo(root.getRight(), value);
		}
	}

	public static void printRecursively(BinaryTreeNode<Integer> root,
			int value, String str) {
		if (root == null)
			return;
		else if (root.getValue() == value) {
			System.out.println((str.isEmpty() ? "" : " -> ") + root);
		} else {
			printRecursively(root.getLeft(), value - root.getValue(),
					(str.isEmpty() ? "" : " -> ") + root);
			printRecursively(root.getRight(), value - root.getValue(),
					(str.isEmpty() ? "" : " -> ") + root);
		}
	}

Problems after running:
INPUT: BST built from sorted array 6 29 35 48 51 56 68 73 79 96 and value = 35.
EXPECTED OUTPUT: 29 -> 6 and 35
OUTPUT: -> 6 and 35.
CORRECTION: Change highlighted line 15, 18 and 20 to:

(str.isEmpty() ? "" : str + " -> ")

Solution:

	public static void findSum(BinaryTreeNode<Integer> head, int sum,
			ArrayList<Integer> buffer, int level) {
		if (head == null)
			return;
		int tmp = sum;
		buffer.add(head.getValue());
		for (int i = level; i > -1; i--) {
			tmp -= buffer.get(i);
			if (tmp == 0)
				print(buffer, i, level);
		}
		ArrayList<Integer> c1 = (ArrayList<Integer>) buffer.clone();
		ArrayList<Integer> c2 = (ArrayList<Integer>) buffer.clone();
		findSum(head.getLeft(), sum, c1, level + 1);
		findSum(head.getRight(), sum, c2, level + 1);
	}

	public static void print(ArrayList<Integer> buffer, int level, int i2) {
		for (int i = level; i <= i2; i++) {
			System.out.print(buffer.get(i) + " ");
		}
		System.out.println();
	}

After reading through the solution, I find there is a bug in my program. As follows:
INPUT: A tree (linked-list) 2 -> 3 -> -4 -> 3 -> 1 -> 2 and value = 5
EXPECTED OUTPUT: 2 ->3, 2 -> 3 -> -4 -> 3 -> 1 and 3 -> -4 -> 3 -> 1 -> 2
OUTPUT: 2 ->3 and 3 -> -4 -> 3 -> 1 -> 2.
The problem is that after we find a path like 2 -> 3, we should not stop right there. If so, we will miss the path like 2 -> 3 -> -4 -> 3 -> 1.
CORRECTION: Discard the ‘else’ block in line 16 and 21.

Determine if a small tree is the subtree of a huge tree

You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

My initial thoughts:
Let us denote the huge tree as T1 and the small tree as T2. We iterate through T1 to see if any node matches the root node of T2. If there’s match, we check if the subtree of T1 is identical to T2. If not, we recursively go deeper.

My initial codes:

	public static boolean isSubtree(BinaryTreeNode<Integer> T1,
			BinaryTreeNode<Integer> T2) {
		if (T1 == null)
			return false;
		else if (T1.getValue().equals(T2.getValue()) && isTwoTreeEqual(T1, T2)) {
			return true;
		} else {
			return isSubtree(T1.getLeft(), T2) || isSubtree(T1.getRight(), T2);
		}
	}

	public static boolean isTwoTreeEqual(BinaryTreeNode<Integer> root1,
			BinaryTreeNode<Integer> root2) {
		if (root1 == null && root2 == null)
			return true;
		else if (root1.isLeaf() && root2.isLeaf())
			return root1.getValue().equals(root2.getValue());
		else if (!root1.isLeaf() && !root2.isLeaf()) {
			if (!root1.getValue().equals(root2.getValue()))
				return false;
			return isTwoTreeEqual(root1.getLeft(), root2.getLeft())
					&& isTwoTreeEqual(root1.getRight(), root2.getRight());
		} else
			return false;
	}

Comments after running:
It works for small trees. When the size goes to 1000, it nearly never finishes. BAD.

Solutions:

	public static boolean containsTree(BinaryTreeNode<Integer> t1,
			BinaryTreeNode<Integer> t2) {
		if (t2 == null)
			return true; // The empty tree is always a subtree
		else
			return subTree(t1, t2);
	}

	private static boolean subTree(BinaryTreeNode<Integer> r1,
			BinaryTreeNode<Integer> r2) {
		if (r1 == null)
			return false; // big tree empty & subtree still not found.
		if (r1.getValue() == r2.getValue()) {
			if (matchTree(r1, r2))
				return true;
		}
		return (subTree(r1.getLeft(), r2) || subTree(r1.getRight(), r2));
	}

	private static boolean matchTree(BinaryTreeNode<Integer> r1,
			BinaryTreeNode<Integer> r2) {
		if (r2 == null && r1 == null)
			return true; // nothing left in the subtree
		if (r1 == null || r2 == null)
			return false; // big tree empty & subtree still not found
		if (r1.getValue() != r2.getValue())
			return false; // data doesn’t match
		return (matchTree(r1.getLeft(), r2.getLeft()) && matchTree(
				r1.getRight(), r2.getRight()));
	}

The solution is very similar to mine except that it handles the case where T2 is null.

Find the 1st common ancestor of two nodes in a binary tree

Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.

My initial thoughts:
Consider two nodes u and v, together with a root node. There are several cases we need to consider:

  1. u is the ancestor of v. then return u.
  2. v is the ancestor of u. then return v.
  3. left subtree of root contains u and right subtree of root contains v. then return root.
  4. left subtree of root contains v and right subtree of root contains u. then return root.

My initial codes:

	public static BinaryTreeNode<Integer> FCA(BinaryTreeNode<Integer> root,
			BinaryTreeNode<Integer> u, BinaryTreeNode<Integer> v) {
		boolean uInLeft = contain(root.getLeft(), u);
		boolean uInRight = contain(root.getRight(), u);
		boolean vInLeft = contain(root.getLeft(), v);
		boolean vInRight = contain(root.getRight(), v);

		if (!uInLeft && !uInRight && !vInLeft && !vInRight)
			return null;

		if (uInLeft && vInRight)
			return root;
		else if (vInLeft && uInRight)
			return root;
		else if (root == u && (vInLeft || vInRight))
			return root;
		else if (root == v && (uInLeft || uInRight))
			return root;
		else {
			BinaryTreeNode<Integer> leftAncestor = FCA(root.getLeft(), u, v);
			BinaryTreeNode<Integer> rightAncestor = FCA(root.getRight(), u, v);
			if (leftAncestor == null && rightAncestor != null)
				return rightAncestor;
			else if (leftAncestor != null && rightAncestor == null)
				return leftAncestor;
			else
				return null;
		}

	}

	public static boolean contain(BinaryTreeNode<Integer> root,
			BinaryTreeNode<Integer> node) {
		if (root == node)
			return true;
		else if (root == null)
			return false;
		else
			return contain(root.getLeft(), node)
					|| contain(root.getRight(), node);
	}

Solution:

	public static BinaryTreeNode<Integer> commonAncestor(
			BinaryTreeNode<Integer> root, BinaryTreeNode<Integer> u,
			BinaryTreeNode<Integer> v) {
		if (contain(root.getLeft(), u) && contain(root.getLeft(), v))
			return commonAncestor(root.getLeft(), u, v);
		if (contain(root.getRight(), u) && contain(root.getRight(), v))
			return commonAncestor(root.getRight(), u, v);
		return root;
	}

Comments: The solution simplifies mine by combing cases.There are actually two simple cases: u and v are along the same side v.s. u and v are on different sides.

Find the in-order successor of a node in a BST

Write an algorithm to find the ‘next’ node (e.g., in-order successor) of a given node in a binary search tree where each node has a link to its parent.

My initial thoughts:
There are three cases:

  1. The node has a right children. Then the ‘next’ node is the left-most node in the right subtree.
  2. The node has no right children but it has a parent.
    • The node is its parent’s left child (i.e., the node is less than its parent): then its parent is its ‘next’ node.
    • The node is its parent’s right child (i.e., the node is greater than its parent): then we climb one level up and examine the parent’s parent.

My initial codes:

	public static BinaryTreeNode2<Integer> findNext(
			BinaryTreeNode2<Integer> root, BinaryTreeNode2<Integer> node) {
		if (node.getRight() != null) {
			// left-most in the right subtree
			BinaryTreeNode2<Integer> rightChild = node.getRight();
			BinaryTreeNode2<Integer> ptr = rightChild;
			while (ptr.getLeft() != null) {
				ptr = ptr.getLeft();
			}
			return ptr;
		}
		if (node.getParent() != null) {
			BinaryTreeNode2<Integer> parent = node.getParent();
			if (parent.getLeft() == node) { // parent is on the right
				return parent;
			} else if (parent.getRight() == node) { // parent is on the left
				BinaryTreeNode2<Integer> ptr = parent;
				while (ptr.getParent() != null) {
					parent = ptr.getParent();
					if (parent.getLeft() == ptr)
						break;
					ptr = parent;
				}
				return parent;
			}
		}
		return null;
	}

Comments after running:
Can’t handle the case where the query node is the right-most node (i.e., the largest number in the sorted array that build this BST, whose ‘next’ node is supposed to be null). The output is the root node. The highlighted lines 18 and 24 make this happen. Because if we climb up all the way from the right-most node, we will end up at the root node. Since the root’s parent is null, the program will return the root. But it’s supposed to return null. Correction (to replace line 18 to 24):

				while (ptr.getParent() != null) {
					parent = ptr.getParent();
					if (parent.getLeft() == ptr)
						return parent;
					ptr = parent;
				}

Also, an edge case should be considered before anything else:

		if(node == null) return null;

Solution:

	public static BinaryTreeNode2 inorderSucc(BinaryTreeNode2 e) {
		if (e != null) {
			BinaryTreeNode2 p;
			// Found right children -> return 1st inorder node on right
			if (e.getParent() == null || e.getRight() != null) {
				p = leftMostChild(e.getRight());
			} else {
				// Go up until we’re on left instead of right (case 2b)
				while ((p = e.getParent()) != null) {
					if (p.getLeft() == e) {
						break;
					}
					e = p;
				}
			}
			return p;
		}
		return null;
	}

	public static BinaryTreeNode2 leftMostChild(BinaryTreeNode2 e) {
		if (e == null)
			return null;
		while (e.getLeft() != null)
			e = e.getLeft();
		return e;
	}

Comments: the solution combine my 2nd and 3rd case together.

Create linked lists of all the nodes at each depth for a BST

Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists)

My initial thoughts:
We just do a level-order traversal throughout the tree. For each level, create a linked list containing all the nodes at that depth. Then extract all of the children for each node to create the next linked list at deeper level.

My initial codes:


	public static List<LinkedList<BinaryTreeNode>> createLinkedLists(
			BinaryTreeNode root) {
		List<LinkedList<BinaryTreeNode>> lists = new ArrayList<LinkedList<BinaryTreeNode>>();
		LinkedList<BinaryTreeNode> level0 = new LinkedList<BinaryTreeNode>();
		level0.add(root);
		lists.add(level0);
		int index = 0;

		while (true) {
			LinkedList<BinaryTreeNode> leveli = new LinkedList<BinaryTreeNode>();
			LinkedList<BinaryTreeNode> upperLevel = lists.get(index);
			for (int i = 0; i < upperLevel.size(); ++i) {
				BinaryTreeNode parent = upperLevel.get(i);
					leveli.add(parent.getLeft());
					leveli.add(parent.getRight());
			}
			if (!leveli.isEmpty()) {
				lists.add(leveli);
				index++;
			} else {
				break;
			}
		}

		return lists;
	}

Comments after running:
NullPointerException in highlighted line 14 and 15. Need to check whether left or right exists before putting into the linked-list. Correction:

				if (parent.getLeft() != null)
					leveli.add(parent.getLeft());
				if (parent.getRight() != null)
					leveli.add(parent.getRight());

Solution:
The solution is identical to my codes:

	public static ArrayList<LinkedList<BinaryTreeNode>> findLevelLinkList(
			BinaryTreeNode root) {
		int level = 0;
		ArrayList<LinkedList<BinaryTreeNode>> result = new ArrayList<LinkedList<BinaryTreeNode>>();
		LinkedList<BinaryTreeNode> list = new LinkedList<BinaryTreeNode>();
		list.add(root);
		result.add(level, list);
		while (true) {
			list = new LinkedList<BinaryTreeNode>();
			for (int i = 0; i < result.get(level).size(); i++) {
				BinaryTreeNode n = result.get(level).get(i);
				if (n != null) {
					if (n.getLeft() != null)
						list.add(n.getLeft());
					if (n.getRight() != null)
						list.add(n.getRight());
				}
			}
			if (list.size() > 0) {
				result.add(level + 1, list);
			} else {
				break;
			}
			level++;
		}
		return result;
	}

Build a binary tree from a sorted array with minimum height

	public static BinaryTreeNode<Integer> buildBinaryTree(Integer[] data,
			int i, int j) {
		if (i == j) {
			return new BinaryTreeNode<Integer>(data[i]);
		} else if (i > j) {
			return null;
		} else {
			int mid = (i + j) / 2;
			BinaryTreeNode<Integer> root = new BinaryTreeNode<Integer>(
					data[mid]);
			root.setLeft(buildBinaryTree(data, i + 1, mid));
			root.setRight(buildBinaryTree(data, mid + 1, j));
			return root;
		}
	}

Comments after running:
Something wrong with indices.
Input: 1 2 3 4 5 6 7
Output:
4
/ \
/ \
3 6
/ \ / \
3 4 6 7
Correction: Highlighted line 11 should be:

root.setLeft(buildBinaryTree(data, i, mid-1));

Solution:
The solution is similar to my codes except that the highlighted line 3 and 4 are not necessary.

Previous Older Entries