DEV Community

Alkesh Ghorpade
Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

LeetCode - Construct Binary Tree from Preorder and Inorder Traversal

Problem statement

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Problem statement taken from: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

Example 1:

Container

Input: preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
Output: [3, 9, 20, null, null, 15, 7]
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]
Enter fullscreen mode Exit fullscreen mode

Constraints:

- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder and inorder consist of unique values.
- Each value of inorder also appears in preorder.
- preorder is guaranteed to be the preorder traversal of the tree.
- inorder is guaranteed to be the inorder traversal of the tree.
Enter fullscreen mode Exit fullscreen mode

Explanation

Brute force approach

The preorder sequence pattern is root-left-right and the inorder sequence is left-root-right. Node 3 in this preorder sequence [3, 9, 20, 15, 7] is the root. We search for node 3 in the inorder sequence. All the elements to the left of 3 in the inorder sequence belong to the left subtree and the elements to the right of it belong to the right subtree.

A C++ snippet of this approach is as follows:

TreeNode* buildTree(int inorder[], int preorder[], int inStart, int inEnd) {
    static int preIndex = 0;

    if (inStart > inEnd)
        return NULL;

    TreeNode* node = newNode(preorder[preIndex++]);

    if (inStart == inEnd)
        return node;

    int inIndex = search(inorder, inStart, inEnd, node->data);

    node->left = buildTree(inorder, preorder, inStart, inIndex - 1);
    node->right = buildTree(inorder, preorder, inIndex + 1, inEnd);

    return node;
}

int search(int arr[], int start, int end, char value) {
    int i;
    for (i = start; i <= end; i++) {
        if (arr[i] == value)
            return i;
    }
}
Enter fullscreen mode Exit fullscreen mode

The time complexity of this approach is O(n^2). The space complexity is O(n). The extra space is due to the recursive call stack.

Efficient solution: Using Map

We can optimize the search function by using hashing. We store the indexes of inorder sequence in a hash map.

A C++ snippet of this approach is as follows:

TreeNode* buildTree(int inorder[], int preorder[], int inStart, int inEnd, unordered_map<int, int>& mp) {
    int preIndex = 0;

    if (inStart > inEnd)
        return NULL;

    int current = preorder[preIndex++];
    TreeNode* tNode = newNode(current);

    if (inStart == inEnd)
        return tNode;

    int inIndex = mp[current];

    tNode->left = buildTree(inorder, preorder, inStart, inIndex - 1, mp);
    tNode->right = buildTree(inorder, preorder, inIndex + 1, inEnd, mp);

    return tNode;
}
Enter fullscreen mode Exit fullscreen mode

The time complexity of this approach is O(n). The space complexity is O(n). The extra space is used to store the elements in the map also due to the recursive function call stack.

Efficient solution: Using Stack

Instead of a map, we can also solve the problem using a stack and set. The stack will be used to store the path we traversed when iterating over the preorder array, and the set is used to maintain the node in which the next right subtree is expected.

Let's check the algorithm to understand it better.

Algorithm

- set TreeNode* root, node = NULL, NULL
  create a set<TreeNode*> s
  create a stack TreeNode* st
  set n = preorder.size()

- loop for pre = 0, in = 0; pre < n
  - set node = NULL

  - loop do
    - node = new TreeNode(preorder[pre])

    - if root == NULL
      - root = node
    - if end

    - if st.size() > 0
      - if s.find(st.top()) != s.end()
        - s.erase(st.top())
        - st.top()->right = node
        - st.pop()
      - else
        - st.top()->left = node
      - if end
    - if end

    - st.push(node)
  - while preorder[pre++] != inorder[in] && pre < n

  - set node = NULL

  - loop while st.size() > 0 && in < n && st.top()->val == inorder[in]
    - node = st.top()
    - st.pop()
    - in++
  - while end

  - if node != NULL
    - s.insert(node)
    - st.push(node)
  - if end
- for end

- return root
Enter fullscreen mode Exit fullscreen mode

Let's check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode* root = NULL;
        TreeNode* node = NULL;
        set<TreeNode*> s;
        stack<TreeNode*> st;
        int n = preorder.size();

        for (int pre = 0, in = 0; pre < n;) {
            node = NULL;
            do {
                node = new TreeNode(preorder[pre]);
                if (root == NULL) {
                    root = node;
                }

                if (st.size() > 0) {
                    if (s.find(st.top()) != s.end()) {
                        s.erase(st.top());
                        st.top()->right = node;
                        st.pop();
                    } else {
                        st.top()->left = node;
                    }
                }
                st.push(node);
            } while (preorder[pre++] != inorder[in] && pre < n);

            node = NULL;

            while(st.size() > 0 && in < n && st.top()->val == inorder[in]) {
                node = st.top();
                st.pop();
                in++;
            }

            if(node != NULL) {
                s.insert(node);
                st.push(node);
            }
        }

        return root;
    }
};
Enter fullscreen mode Exit fullscreen mode

Golang solution

We are using a map instead of a set here.

func buildTree(preorder []int, inorder []int) *TreeNode {
    n := len(preorder)
    if n == 0 {
        return nil
    } else if n == 1 {
        return &TreeNode{Val: preorder[0]}
    }

    root := &TreeNode{Val: preorder[0]}
    st := []*TreeNode{root}

    m := make(map[int]int)
    for i := 0; i < n; i++ {
        m[inorder[i]] = i
    }

    var pop *TreeNode
    for i := 1; i < n; i++ {
        if m[preorder[i]] < m[st[len(st) - 1].Val] {
            pop = st[len(st) - 1]
            pop.Left = &TreeNode{Val: preorder[i]}
            st = append(st, pop.Left)
            continue
        }

        pop = st[len(st) - 1]
        st = st[:len(st) - 1]

        for len(st) > 0 && m[preorder[i]] > m[st[len(st)-1].Val] {
            pop = st[len(st) - 1]
            st = st[:len(st) - 1]
        }

        pop.Right = &TreeNode{Val: preorder[i]}
        st = append(st, pop.Right)
    }

    return root
}
Enter fullscreen mode Exit fullscreen mode

JavaScript solution

var buildTree = function(preorder, inorder) {
    let set = new Set();
    let stack = [];
    let root = null;
    let node = null;
    let n = preorder.length;

    for (let pre = 0, inOrder = 0; pre < n;) {
        node = null;
        do {
            node = new TreeNode(preorder[pre]);
            if (root == null) {
                root = node;
            }

            if (stack.length != 0) {
                if (set.has(stack[stack.length - 1])) {
                    set.delete(stack[stack.length - 1]);
                    stack.pop().right = node;
                } else {
                    stack[stack.length - 1].left = node;
                }
            }

            stack.push(node);
        } while (preorder[pre++] != inorder[inOrder] && pre < preorder.length);

        node = null;
        while (stack.length != 0 && inOrder < n && stack[stack.length - 1].val == inorder[inOrder]) {
            node = stack.pop();
            inOrder++;
        }

        if (node != null) {
            set.add(node);
            stack.push(node);
        }
    }

    return root;
};
Enter fullscreen mode Exit fullscreen mode

Let's dry-run our algorithm for a few examples to see how the solution works.

Input: preorder = [3, 9, 20, 15, 7]
       inorder = [9, 3, 15, 20, 7]

Step 1: TreeNode* root = NULL
        TreeNode* node = NULL
        set<TreeNode*> s
        stack<TreeNode*> st
        int n = preorder.size()
            n = 5

Step 2: loop for pre = 0, in = 0; pre < n
          0 < 5
          true

          loop do
            node = new TreeNode(preorder[pre])
                 = new TreeNode(preorder[0])
                 = new TreeNode(3)

            if root == NULL
               true

               root = node
                    = ->3

            if st.size() > 0
               0 > 0
               false

            st.push(node)
            st.push(->3)

            st = [3]

            while preorder[pre++] != inorder[in] && pre < n
                  preorder[0] != inorder[0] && 1 < 5
                  3 != 9 && true
                  true

            node = new TreeNode(preorder[pre])
                 = new TreeNode(preorder[1])
                 = new TreeNode(9)

            if root == NULL
               3 == NULL
               false

            if st.size() > 0
               1 > 0
               true

               if s.find(st.top()) != s.end()
                  s = []
                  st.top = 3
                  s.find(st.top()) != s.end()
                  s.find(3) != s.end()
                  false
               else
                 st.top()->left = node
                 3->left = 9
               if end

            st.push(node)
            st.push(9)

            st = [3, 9]

            while preorder[pre++] != inorder[in] && pre < n
                  preorder[1] != inorder[0] && 2 < 5
                  9 != 9 && true
                  false
          do end

          node = NULL

          loop while st.size() > 0 && in < n && st.top()->val == inorder[in]
            2 > 0 && 0 < 5 && st.top()->val == inorder[in]
            true && true && 9 == inorder[0]
            true && 9 == 9
            true

            node = st.top()
                 = 9

            st.pop()
            st = [3]

            in++
            in = 1

            while st.size() > 0 && in < n && st.top()->val == inorder[in]
            1 > 0 && 1 < 5 && 3 == inorder[1]
            true && true && 3 == 3
            true

            node = st.top()
                 = 3

            st.pop()
            st = []

            in++
            in = 2

            while st.size() > 0 && in < n && st.top()->val == inorder[in]
            0 > 0 && 2 < 5
            false
          while end

          if node != NULL
             3 != NULL
             true

             s.insert(node)
             s.insert(3)
             s = [3]

             st.push(node)
             st.push(3)
             st = [3]

Step 3: loop for pre < n
          2 < 5
          true

          node = NULL

          loop do
            node = new TreeNode(preorder[pre])
                 = new TreeNode(preorder[2])
                 = new TreeNode(20)

            if root == NULL
               3 == NULL
               false

            if st.size() > 0
               1 > 0
               true

               if s.find(st.top()) != s.end()
                  s = [3]
                  st.top() = 3
                  s.find(3) != s.end()
                  true

                  s.erase(st.top())
                  s.erase(3)
                  s = []

                  st.top()->right = node
                  3->right = 20
                  st.pop()
                  st = []

               st.push(node)
               st = [20]

               while preorder[pre++] != inorder[in] && pre < n
                 preorder[2] != inorder[2] && 3 < 5
                 20 != 15 && true
                 true

            node = new TreeNode(preorder[pre])
                 = new TreeNode(preorder[3])
                 = new TreeNode(15)

            if root == NULL
               3 == NULL
               false

            if st.size() > 0
               1 > 0
               true

               if s.find(st.top()) != s.end()
                  s = []
                  st.top() = 20
                  s.find(20) != s.end()
                  false
               else
                  st.top()->left = node
                  20->left = 15

            st.push(node)
            st = [20, 15]

            while preorder[pre++] != inorder[in] && pre < n
              preorder[3] != inorder[2] && 4 < 5
              15 != 15 && true
              false
          do end

          node = NULL

          loop while st.size() > 0 && in < n && st.top()->val == inorder[in]
            2 > 0 && 2 < 5 && 15 == inorder[2]
            true && 15 == 15

            node = st.top()
                 = 15

            st.pop()
            st = [20]

            in++
            in = 3

          loop while st.size() > 0 && in < n && st.top()->val == inorder[in]
            1 > 0 && 3 < 5 && 20 == inorder[3]
            true && 20 == 20
            true

            node = st.top()
                 = 20

            st.pop()
            st = []

            in++
            in = 4

          loop while st.size() > 0 && in < n && st.top()->val == inorder[in]
            0 > 0
            false

          if node != NULL
             15 != NULL
             true

             s.insert(node)
             s.insert(15)
             s = [15]

             st.push(node)
             st.push(15)
             st = [15]

Step 4: loop for pre < n
          4 < 5
          true

          node = NULL

          loop do
            node = new TreeNode(preorder[pre])
                 = new TreeNode(preorder[4])
                 = new TreeNode(7)

            if root == NULL
               3 == NULL
               false

            if st.size() > 0
               1 > 0
               true

               if s.find(st.top()) != s.end()
                  s = [15]
                  st.top() = 15
                  s.find(st.top()) != s.end()
                  true

                  s.erase(st.top())
                  s.erase(15)
                  s = []

                  st.top()->right = node
                  15->right = 7

                  st.pop()
                  st = []

            st.push(node)
            st = [7]

            while preorder[pre++] != inorder[in] && pre < n
              preorder[4] != inorder[4] && 5 < 5
              7 != 7 && false
              false

            node = NULL

            loop while st.size() > 0 && in < n && st.top()->val == inorder[in]
              1 > 0 && 4 < 5 && 7 == inorder[4]
              true && 7 == 7
              true

              node = st.top()
                   = 7

              st.pop()
              st = []

              in++
              in = 5

            loop while st.size() > 0 && in < n && st.top()->val == inorder[in]
              0 > 0
              false

            if node != NULL
               7 != NULL
               true

               s.insert(node)
               s = [7]

               st.push(node)
               st = [7]

Step 5: loop for pre < n
          5 < 5
          false

Step 6: return root

We return the answer as [3, 9, 20, null, null, 15, 7].
Enter fullscreen mode Exit fullscreen mode

Top comments (0)