Construct Binary Tree From Preorder And Inorder Traversal

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int preIndex = 0;
        unordered_map<int, int> inorderMap;
        for (int i = 0; i < inorder.size(); i++) {
            inorderMap[inorder[i]] = i;
        }
        return build(preorder, inorder, 0, inorder.size() - 1, preIndex, inorderMap);
    }
    
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int inStart, int inEnd, int& preIndex, unordered_map<int, int>& inorderMap) {
        if (inStart > inEnd) {
            return nullptr;
        }
        
        TreeNode* node = new TreeNode(preorder[preIndex++]);
        
        int inIndex = inorderMap[node->val];
        
        node->left = build(preorder, inorder, inStart, inIndex - 1, preIndex, inorderMap);
        node->right = build(preorder, inorder, inIndex + 1, inEnd, preIndex, inorderMap);
        
        return node;
    }
};

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }

        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);

        int rootIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }

        int leftSize = rootIndex - inStart;

        root.left = buildTree(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1);
        root.right = buildTree(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd);

        return root;
    }
}

                                            
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
class Solution(object):
    def buildTree(self, preorder, inorder):
        if inorder:
            root_val = preorder.pop(0)
            root_index = inorder.index(root_val)
            root = TreeNode(root_val)
            root.left = self.buildTree(preorder, inorder[:root_index])
            root.right = self.buildTree(preorder, inorder[root_index + 1:])
            return root

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    if (preorderSize == 0) return NULL;
    
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = preorder[0];
    
    int idx = 0;
    for (int i = 0; i < inorderSize; i++) {
        if (inorder[i] == preorder[0]) {
            idx = i;
            break;
        }
    }
    
    root->left = buildTree(preorder + 1, idx, inorder, idx);
    root->right = buildTree(preorder + idx + 1, preorderSize - idx - 1, inorder + idx + 1, inorderSize - idx - 1);
    
    return root;
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        return BuildTreeHelper(preorder, 0, preorder.Length - 1, inorder, 0, inorder.Length - 1);
    }
    
    private TreeNode BuildTreeHelper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        
        int rootValue = preorder[preStart];
        TreeNode root = new TreeNode(rootValue);

        int rootIndex = Array.IndexOf(inorder, rootValue);

        int leftTreeSize = rootIndex - inStart;

        root.left = BuildTreeHelper(preorder, preStart + 1, preStart + leftTreeSize, inorder, inStart, rootIndex - 1);
        root.right = BuildTreeHelper(preorder, preStart + leftTreeSize + 1, preEnd, inorder, rootIndex + 1, inEnd);

        return root;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var buildTree = function(preorder, inorder) {
    const build = (p_start, p_end, i_start, i_end) => {
        if (p_start > p_end) return null;
        
        const rootVal = preorder[p_start];
        const root = new TreeNode(rootVal);
        
        let rootIndex = i_start;
        while (inorder[rootIndex] !== rootVal) rootIndex++;
        
        const leftSize = rootIndex - i_start;
        
        root.left = build(p_start + 1, p_start + leftSize, i_start, rootIndex - 1);
        root.right = build(p_start + leftSize + 1, p_end, rootIndex + 1, i_end);
        
        return root;
    };
    
    return build(0, preorder.length - 1, 0, inorder.length - 1);
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val === undefined ? 0 : val)
 *         this.left = (left === undefined ? null : left)
 *         this.right = (right === undefined ? null : right)
 *     }
 * }
 */
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    if (preorder.length === 0) return null;
    
    const rootVal = preorder[0];
    const root = new TreeNode(rootVal);
    
    const midIdx = inorder.indexOf(rootVal);
    
    root.left = buildTree(preorder.slice(1, midIdx + 1), inorder.slice(0, midIdx));
    root.right = buildTree(preorder.slice(midIdx + 1), inorder.slice(midIdx + 1));
    
    return root;
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    public $index = 0;
    public $map = [];

    function buildTree($preorder, $inorder) {
        foreach($inorder as $key => $val) {
            $this->map[$val] = $key;
        }
        return $this->helper($preorder, 0, count($preorder) - 1);
    }

    function helper(&$preorder, $start, $end) {
        if($start > $end) {
            return null;
        }
        
        $rootVal = $preorder[$this->index];
        $this->index++;
        $index = $this->map[$rootVal];
        
        $root = new TreeNode($rootVal);
        $root->left = $this->helper($preorder, $start, $index - 1);
        $root->right = $this->helper($preorder, $index + 1, $end);
        
        return $root;
    }
}

                                            
class Solution {
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        if preorder.isEmpty || inorder.isEmpty {
            return nil
        }
        
        let rootVal = preorder[0]
        let root = TreeNode(rootVal)
        
        let rootIndex = inorder.firstIndex(of: rootVal)!
        
        let inorderLeft = Array(inorder[0..<rootIndex])
        let inorderRight = Array(inorder[rootIndex + 1..<inorder.count])
        
        let preorderLeft = Array(preorder[1..<1+inorderLeft.count])
        let preorderRight = Array(preorder[1+inorderLeft.count..<preorder.count])
        
        root.left = buildTree(preorderLeft, inorderLeft)
        root.right = buildTree(preorderRight, inorderRight)
        
        return root
    }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    
    rootVal := preorder[0]
    root := &TreeNode{Val: rootVal}
    
    var mid int
    for i := range inorder {
        if inorder[i] == rootVal {
            mid = i
            break
        }
    }
    
    root.Left = buildTree(preorder[1:mid+1], inorder[:mid])
    root.Right = buildTree(preorder[mid+1:], inorder[mid+1:])
    
    return root
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = 
def build_tree(preorder, inorder)
    return helper(0, 0, inorder.length - 1, preorder, inorder)
end

def helper(pre_start, in_start, in_end, preorder, inorder)
    return nil if pre_start > preorder.length - 1 || in_start > in_end
    
    root = TreeNode.new(preorder[pre_start])
    
    in_index = in_start
    while in_index <= in_end
        break if inorder[in_index] == root.val
        in_index += 1
    end
    
    root.left = helper(pre_start + 1, in_start, in_index - 1, preorder, inorder)
    root.right = helper(pre_start + in_index - in_start + 1, in_index + 1, in_end, preorder, inorder)
    
    return root
end

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
 */

object Solution {
  def buildTree(preorder: Array[Int], inorder: Array[Int]): TreeNode = {
    def helper(preorderStart: Int, preorderEnd: Int, inorderStart: Int, inorderEnd: Int): TreeNode = {
      if (preorderStart > preorderEnd) return null

      val rootValue = preorder(preorderStart)
      val root = new TreeNode(rootValue)

      var inorderRootIdx = inorderStart
      while (inorder(inorderRootIdx) != rootValue) {
        inorderRootIdx += 1
      }

      val leftTreeSize = inorderRootIdx - inorderStart

      root.left = helper(preorderStart + 1, preorderStart + leftTreeSize, inorderStart, inorderRootIdx - 1)
      root.right = helper(preorderStart + leftTreeSize + 1, preorderEnd, inorderRootIdx + 1, inorderEnd)

      root
    }

    helper(0, preorder.length - 1, 0, inorder.length - 1)
  }
}

To solve this coding challenge, you need to construct a binary tree from given preorder and inorder traversal lists. Here's a detailed explanation and pseudocode to help you understand how you can accomplish this task.

Explanation

Preorder Traversal

In a preorder traversal, you visit nodes in the following order:

Root
Left Subtree
Right Subtree

For example, given

[3, 9, 20, 15, 7]

The first element
3

is the root.
The subtree rooted at
3

will have a root of
9

(following nodes as
20, 15, 7

).

Inorder Traversal

In an inorder traversal, you visit nodes in the following order:

Left Subtree
Root
Right Subtree

For example, given

[9, 3, 15, 20, 7]

Nodes to the left of
3

form the left subtree
(9)

.
Nodes to the right of
3

form the right subtree
(15, 20, 7)

.

Steps to Solve the Challenge

Identify the root from the first element of the preorder list.
Find the root's index in the inorder list, which helps in separating the left and right subtrees.
Recursively perform the above steps to construct left and right subtrees.

Detailed Steps in Pseudocode

To clarify these steps, we break down the process into small and very explicit steps.

Base Condition : If the inorder list is empty, return
None

(no more nodes to process).
Root Identification :

Remove the first element from the preorder list; this is the current root.
Find this root’s index in the inorder list.

Subtree Construction :

Elements to the left of the root in the inorder list form the left subtree.
Elements to the right form the right subtree.

Recursive Construction :

Recursively build the left subtree by passing the corresponding segments of preorder and inorder lists.
Recursively build the right subtree similarly.

Pseudocode

                                            
// Function to build the tree from preorder and inorder traversal lists
function buildTree(preorder, inorder):
    // Base case: if inorder list is empty, return None
    if inorder is empty:
        return None

    // Get the root value from the preorder list (first element)
    root_value = preorder.pop(0)

    // Find the index of the root in the inorder list
    root_index = findIndex(inorder, root_value)

    // Create the root node
    root_node = TreeNode(root_value)

    // Build the left subtree by taking elements before root_index in inorder
    root_node.left = buildTree(preorder, inorder[0:root_index])
    
    // Build the right subtree by taking elements after root_index in inorder
    root_node.right = buildTree(preorder, inorder[root_index + 1:end])

    // Return the constructed root_node
    return root_node

// Helper function to find the index of a value in a list
function findIndex(list, value):
    for i from 0 to length(list) - 1:
        if list[i] == value:
            return i
    return -1

In the pseudocode:

buildTree

is a recursive function that constructs the binary tree.
preorder.pop(0)

removes and returns the first element of the preorder list, giving us the current root node.
findIndex

is a helper function to locate the index of a value in the list. This is necessary to determine which elements belong to the left and right subtrees in the inorder sequence.
When we make recursive calls to
buildTree

, the portions of the lists corresponding to the left and right subtrees are passed by slicing the inorder list around the root index.

To summarize, this methodology leverages the properties of preorder and inorder traversals to systematically build the tree by recursively partitioning the lists into left and right subtrees and creating nodes accordingly. This detailed and systematic approach ensures a correct tree reconstruction process.