Common Binary Trees Examples
21 Oct 2017
View Comments
#binary
#tree
#traversal
#programming
#examples
Last week, we took a peek at the basic traits of the binary trees and there were few code examples alongside. However, it isn’t nearly enough to apply these understanding to a real-life example. I would like to go over some simple tree exercises which I believe illustrates what the binary tree is in a good way. The examples here are mostly done in recursion, but they probably could be solved iteratively as well.
For all the examples below, let’s assume that we have a TreeNode structured available like below:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int data) {
this.val = val;
this.left = null;
this.right = null;
}
}1. Invert a binary tree
Let’s start off with a famous tree problem of inverting a binary tree. One day, Max Howell (creator of the HomeBrew) tweeted saying that “Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off”. Wow, that is a pretty bold statement, but understandable.
Problem statement: “Invert a binary tree.”
Here is a visual example of what inverting a tree means:
4
/ \
2 7
/ \ / \
1 3 6 9to
4
/ \
7 2
/ \ / \
9 6 3 1The problem is pretty simple when you have a visual example like above. It is solved using a BFS tree traversal (as we went over in the previous blog post). We can swap the left and right child as we go along BFS traversing the tree iteratively.
Code solution:
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
return root;
}2. Lowest Common Ancestor of a Binary Search Tree (BST)
Here is another quite popular algorithm for a binary tree, searching for the lowest common ancestor.
Problem statement:
“Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.”
Example:
_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5With above tree,
- the LCA of nodes
2and8is6 - the LCA of nodes
2and4is2
Code solution:
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
if (root.val < p.val && root.val < q.val) { //search right
root = root.right;
} else if (root.val > p.val && root.val > q.val) { //search left
root = root.left;
} else { //found
return root;
}
}
return null;
}Above algorithm is solved iteratively rather than recursively. We could certainly have solved the algorithm recursively. If you would like to solve this problem in recursion, it is indeed simpler. You can just return the function itself creating a recursion when those if conditions are met in the loop. You would need the base case for the recursion to avoid infinite recursion.
3. LCA of a Binary Tree (instead of BST)
I can see some of you may have asked yourself, what if it isn’t binary search tree? Well, the problem isn’t so simple anymore. In above BST case, things were good-looking where we can get an amazing worst time complexity of O(h) where h is the height of the tree. In a balanced tree, this means we can get an amazing complexity of our famous \(O(log_2(n))\). Unfortunately, with a binary tree case, we are required to search the whole tree to find our nodes. So the worst case time complexity is O(n) for this case where n is equal to every node of the tree.
Problem statement:
“Given a binary tree (not a binary search tree) and two values say n1 and n2, write a program to find the least common ancestor.”
It is a basically same problem as above problem (#2), but we do not have binary search tree features anymore.
Code solution:
public TreeNode lca(TreeNode root, TreeNode a, TreeNode b) {
if (root == null) {
return null;
}
if (root.equals(a) || root.equals(b)) {
return root;
}
TreeNode left = lca(root.left, a, b);
TreeNode right = lca(root.right, a, b);
if (left != null && right != null ) return root;
if (left == null) return right;
else return left;
}Let’s analyze the code a bit. This piece of code might confuse you as it did for me a lot. The code is traversing the tree using a post-order DFS with a few conditions. First, it traverses the tree all the way to left unless we have a hit the node a or b which are the 2 base nodes to get the lowest common ancestor. Then we will recurse to locate a and b in the tree. At the time when both left and right are defined, we have found the lowest common ancestor. Using the post-order DFS is important here as we need to make sure the parent nodes are hit the last to ensure that we have the ultimate parent node.
4. Symmetric Tree
Problem statement:
“Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).”
For example, this binary tree is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3But the following tree is not:
1
/ \
2 2
\ \
3 3because of those 3s are not mirroring themselves.
Code solution:
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
if (root.left == null && root.right == null) return true;
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode left, TreeNode right) {
if (left == null && right == null) return true;
if (left == null || right == null) return false;
return (left.val == right.val) && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
}This straightforward example is another DFS variation (pre-order) which checks the value as it traverses 2 trees at the same time. It is simply checking the left node’s left child must be equal to the right node’s right child; vice-versa. We could have solved this using BFS traversal as well. Basically instead of one queue, track iteratively with 2 separate queues. Then for each level, check the child nodes symmetry like similar to above code, left.val != right.val. In my opinion, both solutions make good sense. Intuitively for me, BFS solution came into my mind first but I presented DFS solution because this solution is pretty easy to understand and follow through.
5. Minimum height
Problem statement:
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.”
Here is a visual example:
_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5The height should be 2 here. One example of a height 2 is found at 6->2->0 which has the minimum height in above tree.
Code solution:
public int minDepth(TreeNode root) {
if (root == null)
return 0;
int depth = 1;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
TreeNode temp, magic = new TreeNode(0);
queue.add(root);
queue.add(magic);
while (!queue.isEmpty()) {
temp = queue.poll();
if (temp == magic) {
if (!queue.isEmpty()) {
depth++;
queue.add(magic);
}
continue;
}
if (temp.left == null && temp.right == null)
return depth;
if (temp.left != null)
queue.add(temp.left);
if (temp.right != null)
queue.add(temp.right);
}
return depth;
}A simple and intuitive BFS traversal solution. The algorithm traverses level by level which checks whether it encounters a node with no children (both left and right child nodes are null). Meanwhile, it tracks the count of levels (depth) by adding a magic node to indicate the end of the level. After it found a node with no children, it simply returns the depth it has been counting.
Conclusion
The tree problem is often solved using either DFS or BFS traversal. If you are planning to use DFS, the problem can be further reduced by choosing one of pre/in/post -order traversal. If you would like to know the distinct benefits of these 3 variations of DFS traversal, please check out my previous post. In this post, we saw some examples that are really fundamentals to the binary trees. There are binary trees which can also be self-balancing, such as AVL or Red-Black tree. It adds a slight complication to the algorithm as it requires the tree to rotate as it is self-balancing. However, the majority of the tree fundamentals stay the same. It prevents the tree being skewed to one side which could cut down worst-case time complexity by letting the tree always stay balanced. Trees are not always binary though. The number of leaves can, in fact, be more than 2. They are sometimes called ternary trees, quaternary trees and so on. However, we just normally call it an n-ary tree. There can be as many numbers of children in the tree. There are certainly added complications on operations to this kind of tree. However, more leaves often lead to a slower performance. For instance, you may think ternary search is faster than binary search as \(log_3(n)\) produces smaller value than \(log_2(n)\). However, this is quite misleading because when tree node has more than choices of 2, it no longer can apply one comparison per iteration. So in the end, it becomes slower. There is also a tree structure called a trie which can have any # of children as well. It is useful to auto-completing something which could be applied in searching a set of words in the dictionary. Anyways, in my view, a tree is just another object (node) which is made up to be a data structure like a linked list with strict rules. When we know exactly what we are expecting, the algorithm can improve significantly. If you are looking for more tree examples, I suggest you take a look at my GitHub. I have summarized some common tree problems there.
