Tag Archives: Tree

Binary Tree Postorder Traversal Non-recursive Version

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},


return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

(Java Code on Github at the bottom of the post. )

My thoughts and solutions:

Well the recursive solution is indeed trivial but quite elegant. However, sometimes we may hit a stack overflow exception and that’s why we need the iterative version. To convert a recursive solution into an iterative one, we have to implement our own stack.

So what should we put in our own stack? Think about the recursive version. For example, for each node that does not satisfy the condition of the base case, the function immediately calls on itself with the current node’s left child (if it exists), leaving its right child (if it exists) and its current value unprocessed. So the items going to the stack are nodes that are not fully processed: either its left or right child has not been visited yet.

So the stack is for tree nodes, but we also need to know whether the children of each node have been visited. The original node class does not support this. One simple solution is to wrap the TreeNode class in another class and I call it NodeInfo (it is a private class inside the PostorderTraversal class) and we create a stack of NodeInfo:

 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
private class NodeInfo{
    TreeNode node;
    boolean isLeftVisited;
    boolean isRightVisited;
    public NodeInfo(TreeNode node){
        this.node = node;
        isLeftVisited = false;
        isRightVisited = false;
        if(node.left == null) isLeftVisited = true;
        if(node.right == null) isRightVisited = true;

OK, how does this work? Remember that for post order traversal, it has the following order:

  • Visit left subtree
  • Visit right subtree
  • Visit current node

So we can push our root wrapped in NodeInfo object to the stack. Then, as long as the stack is not empty:

  • we peek at the top node.
  • if the node has left child and it is not visited, set isLeftVisited to true and visitSubtree(left)
  • else if the node has right child and it is not visited, set isRightVisited to true and visitSubtree(right)
  • else if both children are visited, pop the top node and add its value to an ArrayList solution.

How do we visit the subtree?

while the node is not a leaf:

  • push itself to the stack
  • if it has unvisited  left child, set isLeftVisited to true and point itself to its left child
  • else if it has unvisited  right child, set isRightVisited to true and point itself to its right child

When the loop ends, the node should point to a leaf node so just add its value to the ArrayList solution.

I had trouble at first worrying about visiting only one side of a node in the loop, like we are missing them. But then I realized that all nodes with unvisited children are push to the stack along the way to the leaves so no worries.

Code on github:

Enhanced by Zemanta

Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

   / \
  2   2
   \   \
   3    3

Bonus points if you could solve it both recursively and iteratively.

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

This problem looks simple, but actually is a little tricky. Usually when I see a problem like this I immediately think of recursion and come to the following wrong conclusion: the whole tree is symmetric when subtrees are symmetric. I stuck with this idea for a few minutes and then realized that this is not true.

   /   \
  2     4
 / \   / \
3   3 3   3

The subtrees of the tree above are symmetric but the whole tree is not.

How do we human check if something is symmetric? In this case, we would probably check one node on the left side and compare with node at its mirroring position on the right. If they are the same, we move on to another node. Otherwise it is not symmetric.

So we are actually traversing the trees and along the way we check if a certain pair of nodes in mirroring positions have the same value.

As for tree traversal, we have breadth-first and depth-first traversals. But we may have to make some modifications.

Using the following tree as an example:

   /   \
  N2    N3
 / \   / \
N4 N5 N6 N7
  • Breadth-First: in a normal situation, we would use a queue, starting from the root and keeping adding the child nodes.  The queue would be N1, N2, N3, N4, N5, N6, N7. But since we need the mirroring effect, the queue should be N1, N2, N3, N4, N7, N5, N6. So think about how to achieve this order when dealing with nodes. When comparing, we have to dequeue two nodes at a time (except for the root of the tree N1).
  • Depth-First: in this case, say we want to use recursion. Basically we traverse the left subtree from N2 and do the same for N3. We won’t be able to compare two nodes in mirroring position along the way. So we have to save the values somewhere. I say we use a stack. The order of the two traversals should be like this: left side should be N2, N4, N5 while right side should be N3, N7, N6. Each time we meet a node, we push its value to the stack and go to their child nodes. If a child node is null, we must push null to the stack too! Otherwise it will fail on the second example in this post.

Code on github:

Enhanced by Zemanta

Algorithm I, Part I — Union By Height

Q: Union-by-height. Develop a union-find implementation that uses the same basic strategy as weighted quick-union but keeps track of tree height and always links the shorter tree to the taller one. Prove a lgN upper bound on the height of the trees for N sites with your algorithm.

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

This one should be simple if you know how to union by size. Just change the array that holds the size of tree to an array that holds the height of the tree. And if a shorter tree connects to a taller tree, the height of the new tree is the same as the old tall tree. So when does the tree height increase? Well, the answer is that when two trees with the same height union together.

As for the upper bound of the height of the tree for N sites, let’s think about the worst case that we union objects in pairs to create trees with the same height and keep doing it until we end up with a single tree. The tree height always increases, but at most lgN times (since we are union things in pair). If on any level, we break this rule, we increase less.

Level 1: 1    2    3   4    5   6   7   8

Level 2: 1-2    3-4   5-6    7-8

Level 3: 1-2-3-4   5-6-7-8

Level 4: 1-2-3-4-5-6-7-8

Code on github:

Enhanced by Zemanta