Construct binary tree given its inorder and preorder traversals without recursion

Question

Given inorder and preorder traversals of a tree, how the tree can be re-constructed in non-recursive manner.

For example:

Re-construct the following tree

                     1
       2                             3
 4           5                6             7
                  8                     9

given

inorder traversal: 4, 2, 5, 8, 1, 6, 3, 9, 7

preorder traversal: 1, 2, 4, 5, 8, 3, 6, 7, 9

Note: There are many references to recursive implementations. For example, one may refer Construct Tree from given Inorder and Preorder traversals. However intent here is to find non-recursive implementation.

Recursion uses the call stack to hold information. To do the same thing without recursion, simply create a data stack to hold that information. — user3386109

Vasu Vasu · Accepted Answer · 2018-01-21T05:42:58

Idea is to keep tree nodes in a stack from preorder traversal, till their counterpart is not found in inorder traversal. Once a counterpart is found, all children in the left sub-tree of the node must have been already visited.

Following is non-recursive Java implementation.

public TreeNode constructTree(int[] preOrder, int[] inOrder) {

    if (preOrder.length == 0) {
      return null;
    }

    int preOrderIndex = 0;
    int inOrderIndex = 0;

    ArrayDeque<TreeNode> stack = new ArrayDeque<>();

    TreeNode root = new TreeNode(preOrder[0]);
    stack.addFirst(root);
    preOrderIndex++;

    while (!stack.isEmpty()) {

      TreeNode top = stack.peekFirst();

      if (top.val == inOrder[inOrderIndex]) {

        stack.pollFirst();
        inOrderIndex++;

        // if all the elements in inOrder have been visted, we are done
        if (inOrderIndex == inOrder.length) {
          break;
        }

        // Check if there are still some unvisited nodes in the left
        // sub-tree of the top node in the stack
        if (!stack.isEmpty()
            && stack.peekFirst().val == inOrder[inOrderIndex]) {
          continue;
        }

        // As top node in stack, still has not encontered its counterpart
        // in inOrder, so next element in preOrder must be right child of
        // the removed node
        TreeNode node = new TreeNode(preOrder[preOrderIndex]);
        preOrderIndex++;
        top.right = node;
        stack.addFirst(node);

      } else {
        // Top node in the stack has not encountered its counterpart
        // in inOrder, so next element in preOrder must be left child
        // of this node
        TreeNode node = new TreeNode(preOrder[preOrderIndex]);
        preOrderIndex++;
        top.left = node;
        stack.addFirst(node);
      }
    }

    return root;
  }

Construct binary tree given its inorder and preorder traversals without recursion

1 Answers