Construct Tree from Traversals

Overview

Tree construction from traversals is a fundamental problem in computer science that involves rebuilding a binary tree structure given specific traversal sequences. This technique is crucial for understanding tree properties, serialization/deserialization, and various algorithmic applications.

Key Principles

Traversal Order Properties

1. Pre-order: Root → Left → Right (Root first)
2. In-order: Left → Root → Right (In-between)
3. Post-order: Left → Right → Root (Root last)
4. Level-order: Breadth-first, left-to-right

Essential Properties for Construction

• Pre-order: First element is always root
• In-order: Elements to left of root are in left subtree, right elements in right subtree
• Post-order: Last element is always root
• Level-order: Elements processed level by level

Construct from Pre-order and In-order

Algorithm Approach

function buildTreeFromPreIn(preorder, inorder) {
    if (preorder.length === 0 || inorder.length === 0) return null;
    
    // First element in pre-order is root
    const rootVal = preorder[0];
    const root = new TreeNode(rootVal);
    
    // Find root position in in-order
    const rootIndex = inorder.indexOf(rootVal);
    
    // Split in-order into left and right subtrees
    const leftInOrder = inorder.slice(0, rootIndex);
    const rightInOrder = inorder.slice(rootIndex + 1);
    
    // Split pre-order into left and right subtrees
    const leftPreOrder = preorder.slice(1, 1 + leftInOrder.length);
    const rightPreOrder = preorder.slice(1 + leftInOrder.length);
    
    // Recursively build subtrees
    root.left = buildTreeFromPreIn(leftPreOrder, leftInOrder);
    root.right = buildTreeFromPreIn(rightPreOrder, rightInOrder);
    
    return root;
}

Implementation Details

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function buildTreeFromPreIn(preorder, inorder) {
    if (preorder.length === 0 || inorder.length === 0) return null;
    
    // Create root from pre-order (first element)
    const rootVal = preorder[0];
    const root = new TreeNode(rootVal);
    
    // Find root position in in-order
    const rootIndex = inorder.indexOf(rootVal);
    
    // Split in-order into left and right subtrees
    const leftInOrder = inorder.slice(0, rootIndex);
    const rightInOrder = inorder.slice(rootIndex + 1);
    
    // Split pre-order into left and right subtrees
    const leftPreOrder = preorder.slice(1, 1 + leftInOrder.length);
    const rightPreOrder = preorder.slice(1 + leftInOrder.length);
    
    // Recursively build subtrees
    root.left = buildTreeFromPreIn(leftPreOrder, leftInOrder);
    root.right = buildTreeFromPreIn(rightPreOrder, rightInOrder);
    
    return root;
}

Example Trace

Pre-order: [3, 9, 20, 15, 7]
In-order:  [9, 3, 15, 20, 7]

Step 1: Root = 3 (first in pre-order)
       In-order split: [9] | [15, 20, 7]

Step 2: Left subtree: pre=[9], in=[9]
        Right subtree: pre=[20, 15, 7], in=[15, 20, 7]

Step 3: Build left subtree with root=9
        Build right subtree with root=20

Construct from Post-order and In-order

Algorithm Approach

function buildTreeFromPostIn(postorder, inorder) {
    if (postorder.length === 0 || inorder.length === 0) return null;
    
    // Last element in post-order is root
    const rootVal = postorder[postorder.length - 1];
    const root = new TreeNode(rootVal);
    
    // Find root position in in-order
    const rootIndex = inorder.indexOf(rootVal);
    
    // Split in-order into left and right subtrees
    const leftInOrder = inorder.slice(0, rootIndex);
    const rightInOrder = inorder.slice(rootIndex + 1);
    
    // Split post-order into left and right subtrees
    const leftPostOrder = postorder.slice(0, leftInOrder.length);
    const rightPostOrder = postorder.slice(leftInOrder.length, postorder.length - 1);
    
    // Recursively build subtrees
    root.left = buildTreeFromPostIn(leftPostOrder, leftInOrder);
    root.right = buildTreeFromPostIn(rightPostOrder, rightInOrder);
    
    return root;
}

Implementation Details

function buildTreeFromPostIn(postorder, inorder) {
    if (postorder.length === 0 || inorder.length === 0) return null;
    
    // Last element in post-order is root
    const rootVal = postorder[postorder.length - 1];
    const root = new TreeNode(rootVal);
    
    // Find root position in in-order
    const rootIndex = inorder.indexOf(rootVal);
    
    // Split in-order into left and right subtrees
    const leftInOrder = inorder.slice(0, rootIndex);
    const rightInOrder = inorder.slice(rootIndex + 1);
    
    // Split post-order into left and right subtrees
    const leftPostOrder = postorder.slice(0, leftInOrder.length);
    const rightPostOrder = postorder.slice(leftInOrder.length, postorder.length - 1);
    
    // Recursively build subtrees
    root.left = buildTreeFromPostIn(leftPostOrder, leftInOrder);
    root.right = buildTreeFromPostIn(rightPostOrder, rightInOrder);
    
    return root;
}

Example Trace

Post-order: [9, 15, 7, 20, 3]
In-order: [9, 3, 15, 20, 7]

Step 1: Root = 3 (last in post-order)
       In-order split: [9] | [15, 20, 7]

Step 2: Left subtree: post=[9], in=[9]
        Right subtree: post=[15, 7, 20], in=[15, 20, 7]

Step 3: Build left subtree with root=9
        Build right subtree with root=20

Construct from Level-order

Algorithm Approach

function buildTreeFromLevelOrder(levelOrder) {
    if (levelOrder.length === 0) return null;
    
    const root = new TreeNode(levelOrder[0]);
    const queue = [root];
    let i = 1;
    
    while (queue.length > 0 && i < levelOrder.length) {
        const node = queue.shift();
        
        // Add left child
        if (i < levelOrder.length) {
            node.left = new TreeNode(levelOrder[i++]);
            queue.push(node.left);
        }
        
        // Add right child
        if (i < levelOrder.length) {
            node.right = new TreeNode(levelOrder[i++]);
            queue.push(node.right);
        }
    }
    
    return root;
}

Implementation Details

function buildTreeFromLevelOrder(levelOrder) {
    if (levelOrder.length === 0) return null;
    
    const root = new TreeNode(levelOrder[0]);
    const queue = [root];
    let i = 1;
    
    while (queue.length > 0 && i < levelOrder.length) {
        const node = queue.shift();
        
        // Add left child if available
        if (i < levelOrder.length) {
            node.left = new TreeNode(levelOrder[i++]);
            queue.push(node.left);
        }
        
        // Add right child if available
        if (i < levelOrder.length) {
            node.right = new TreeNode(levelOrder[i++]);
            queue.push(node.right);
        }
    }
    
    return root;
}

Example Trace

Level-order: [3, 9, 20, null, null, 15, 7]

Step 1: Root = 3
       Queue: [3]

Step 2: Process node 3, add children 9 and 20
       Queue: [9, 20]

Step 3: Process node 9, add children null and null
       Queue: [20]

Step 4: Process node 20, add children 15 and 7
       Queue: [null, null, 15, 7]

Complete Tree Construction Suite

Comprehensive Implementation

class TreeConstructor {
    // Build from pre-order and in-order
    static buildFromPreIn(preorder, inorder) {
        if (!preorder || !inorder || 
            preorder.length === 0 || inorder.length === 0) {
            return null;
        }
        
        const root = new TreeNode(preorder[0]);
        const rootIndex = inorder.indexOf(preorder[0]);
        
        if (rootIndex === -1) return null;
        
        const leftInOrder = inorder.slice(0, rootIndex);
        const rightInOrder = inorder.slice(rootIndex + 1);
        
        const leftPreOrder = preorder.slice(1, 1 + leftInOrder.length);
        const rightPreOrder = preorder.slice(1 + leftInOrder.length);
        
        root.left = this.buildFromPreIn(leftPreOrder, leftInOrder);
        root.right = this.buildFromPreIn(rightPreOrder, rightInOrder);
        
        return root;
    }
    
    // Build from post-order and in-order
    static buildFromPostIn(postorder, inorder) {
        if (!postorder || !inorder || 
            postorder.length === 0 || inorder.length === 0) {
            return null;
        }
        
        const rootVal = postorder[postorder.length - 1];
        const root = new TreeNode(rootVal);
        const rootIndex = inorder.indexOf(rootVal);
        
        if (rootIndex === -1) return null;
        
        const leftInOrder = inorder.slice(0, rootIndex);
        const rightInOrder = inorder.slice(rootIndex + 1);
        
        const leftPostOrder = postorder.slice(0, leftInOrder.length);
        const rightPostOrder = postorder.slice(leftInOrder.length, postorder.length - 1);
        
        root.left = this.buildFromPostIn(leftPostOrder, leftInOrder);
        root.right = this.buildFromPostIn(rightPostOrder, rightInOrder);
        
        return root;
    }
    
    // Build from level-order
    static buildFromLevelOrder(levelOrder) {
        if (!levelOrder || levelOrder.length === 0) return null;
        
        const root = new TreeNode(levelOrder[0]);
        const queue = [root];
        let i = 1;
        
        while (queue.length > 0 && i < levelOrder.length) {
            const node = queue.shift();
            
            // Add left child
            if (i < levelOrder.length && levelOrder[i] !== null) {
                node.left = new TreeNode(levelOrder[i]);
                queue.push(node.left);
            }
            i++;
            
            // Add right child
            if (i < levelOrder.length && levelOrder[i] !== null) {
                node.right = new TreeNode(levelOrder[i]);
                queue.push(node.right);
            }
            i++;
        }
        
        return root;
    }
    
    // Validate if construction is possible
    static canBuildFromPreIn(preorder, inorder) {
        // Basic validation
        if (!preorder || !inorder) return false;
        
        // Check if lengths match
        if (preorder.length !== inorder.length) return false;
        
        // Check if all elements in preorder exist in inorder
        const inorderSet = new Set(inorder);
        for (const val of preorder) {
            if (!inorderSet.has(val)) return false;
        }
        
        return true;
    }
}

Time and Space Complexity

| Method | Time Complexity | Space Complexity |

|--------|--------------|---------------|

| Pre-order + In-order | O(n²) | O(n) |

| Post-order + In-order | O(n²) | O(n) |

| Level-order | O(n) | O(w) |

Where:

• n = number of nodes in tree
• w = maximum width of tree (queue space)

Common Variations and Challenges

1. Handling Duplicate Values

function buildTreeWithDuplicates(preorder, inorder) {
    // Handle cases where values might be duplicated
    const rootVal = preorder[0];
    const rootIndex = inorder.indexOf(rootVal);
    
    // If multiple occurrences, need to track position more carefully
    return buildTreeFromPreIn(preorder, inorder);
}

2. Null Value Handling

function buildTreeWithNulls(levelOrder) {
    // Handle null values in level-order sequences
    if (!levelOrder || levelOrder.length === 0) return null;
    
    const root = new TreeNode(levelOrder[0]);
    const queue = [root];
    let i = 1;
    
    while (queue.length > 0 && i < levelOrder.length) {
        const node = queue.shift();
        
        // Handle null values properly
        if (i < levelOrder.length && levelOrder[i] !== null) {
            node.left = new TreeNode(levelOrder[i]);
            queue.push(node.left);
        }
        i++;
        
        if (i < levelOrder.length && levelOrder[i] !== null) {
            node.right = new TreeNode(levelOrder[i]);
            queue.push(node.right);
        }
        i++;
    }
    
    return root;
}

3. Optimized Pre-order + In-order

function buildOptimizedPreIn(preorder, inorder) {
    const indexMap = new Map();
    
    // Build map for O(1) lookup
    for (let i = 0; i < inorder.length; i++) {
        indexMap.set(inorder[i], i);
    }
    
    function build(preStart, preEnd, inStart, inEnd) {
        if (preStart > preEnd || inStart > inEnd) return null;
        
        const rootVal = preorder[preStart];
        const rootIndex = indexMap.get(rootVal);
        
        const leftSize = rootIndex - inStart;
        
        const root = new TreeNode(rootVal);
        root.left = build(preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
        root.right = build(preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
        
        return root;
    }
    
    return build(0, preorder.length - 1, 0, inorder.length - 1);
}

Common Mistakes to Avoid

1. Incorrect Index Calculation

// ❌ Wrong - Incorrect array slicing logic
function wrongPreInBuild(preorder, inorder) {
    const root = new TreeNode(preorder[0]);
    
    // Wrong: assuming same length for all subarrays
    const rootIndex = inorder.indexOf(preorder[0]);
    
    // This doesn't properly handle array slicing
    const leftPre = preorder.slice(1, rootIndex);
    const rightPre = preorder.slice(rootIndex + 1);
    
    return root;
}

2. Missing Base Case Handling

// ❌ Wrong - Not handling edge cases properly
function incompleteBuild(preorder, inorder) {
    // Missing null checks and empty array handling
    
    const root = new TreeNode(preorder[0]);
    
    // This will fail if arrays are empty or have different lengths
    const rootIndex = inorder.indexOf(preorder[0]);
    
    return root;
}

3. Incorrect Subtree Splitting

// ❌ Wrong - Not properly splitting subtrees
function wrongSubtreeSplit(preorder, inorder) {
    const root = new TreeNode(preorder[0]);
    
    // Wrong: assuming same indices work for both arrays
    const rootIndex = inorder.indexOf(preorder[0]);
    
    // This logic is flawed for subtree division
    const leftInOrder = inorder.slice(0, rootIndex);
    const rightInOrder = inorder.slice(rootIndex + 1);
    
    // Incorrect calculation of pre-order ranges
    const leftPreOrder = preorder.slice(1, rootIndex + 1);
    
    return root;
}

Real-World Applications

1. Serialization/Deserialization

// Serialize tree to pre-order with null markers
function serializeTree(root) {
    const result = [];
    
    function dfs(node) {
        if (node === null) {
            result.push(null);
            return;
        }
        
        result.push(node.val);
        dfs(node.left);
        dfs(node.right);
    }
    
    dfs(root);
    return result;
}

// Deserialize from pre-order array
function deserializeTree(data) {
    let index = 0;
    
    function build() {
        if (index >= data.length || data[index] === null) {
            index++;
            return null;
        }
        
        const node = new TreeNode(data[index++]);
        node.left = build();
        node.right = build();
        
        return node;
    }
    
    return build();
}

2. Database Index Reconstruction

// Reconstruct B-tree structure from stored traversal data
class DatabaseIndexTree {
    constructor() {
        this.root = null;
    }
    
    rebuildFromTraversals(preorder, inorder) {
        this.root = TreeConstructor.buildFromPreIn(preorder, inorder);
    }
    
    reconstructFromLevelOrder(levelData) {
        this.root = TreeConstructor.buildFromLevelOrder(levelData);
    }
}

3. File System Tree Reconstruction

// Rebuild directory structure from traversal logs
class FileSystemTree {
    constructor() {
        this.root = null;
    }
    
    rebuildFromTraversal(logs) {
        // Parse logs and reconstruct tree structure
        const levelOrder = this.parseLogsToLevelOrder(logs);
        this.root = TreeConstructor.buildFromLevelOrder(levelOrder);
    }
}

Performance Optimization Tips

1. Use Hash Maps for Index Lookup

function optimizedPreInBuild(preorder, inorder) {
    const indexMap = new Map();
    
    // Precompute indices for O(1) lookup
    for (let i = 0; i < inorder.length; i++) {
        indexMap.set(inorder[i], i);
    }
    
    function build(preStart, preEnd, inStart, inEnd) {
        if (preStart > preEnd || inStart > inEnd) return null;
        
        const rootVal = preorder[preStart];
        const rootIndex = indexMap.get(rootVal);
        
        const leftSize = rootIndex - inStart;
        
        const root = new TreeNode(rootVal);
        root.left = build(preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
        root.right = build(preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
        
        return root;
    }
    
    return build(0, preorder.length - 1, 0, inorder.length - 1);
}

2. Iterative Approach for Large Trees

function iterativeTreeBuild(levelOrder) {
    if (levelOrder.length === 0) return null;
    
    const root = new TreeNode(levelOrder[0]);
    const queue = [root];
    let i = 1;
    
    while (queue.length > 0 && i < levelOrder.length) {
        const node = queue.shift();
        
        // Add left child
        if (i < levelOrder.length && levelOrder[i] !== null) {
            node.left = new TreeNode(levelOrder[i]);
            queue.push(node.left);
        }
        i++;
        
        // Add right child
        if (i < levelOrder.length && levelOrder[i] !== null) {
            node.right = new TreeNode(levelOrder[i]);
            queue.push(node.right);
        }
        i++;
    }
    
    return root;
}

Common Interview Patterns

Pattern 1: Basic Construction

function constructBinaryTree(preorder, inorder) {
    if (preorder.length === 0 || inorder.length === 0) return null;
    
    const root = new TreeNode(preorder[0]);
    const rootIndex = inorder.indexOf(preorder[0]);
    
    const leftInOrder = inorder.slice(0, rootIndex);
    const rightInOrder = inorder.slice(rootIndex + 1);
    
    const leftPreOrder = preorder.slice(1, 1 + leftInOrder.length);
    const rightPreOrder = preorder.slice(1 + leftInOrder.length);
    
    root.left = constructBinaryTree(leftPreOrder, leftInOrder);
    root.right = constructBinaryTree(rightPreOrder, rightInOrder);
    
    return root;
}

Pattern 2: Multiple Traversal Types

function handleMultipleTraversals(preorder, inorder, postorder) {
    // Validate that all traversals are consistent
    const canBuildPreIn = TreeConstructor.canBuildFromPreIn(preorder, inorder);
    
    if (canBuildPreIn) {
        return TreeConstructor.buildFromPreIn(preorder, inorder);
    }
    
    // Try post-in order
    return TreeConstructor.buildFromPostIn(postorder, inorder);
}

Pattern 3: Serialization with Reconstruction

class TreeSerializer {
    static serialize(root) {
        const result = [];
        
        function dfs(node) {
            if (node === null) {
                result.push('null');
                return;
            }
            
            result.push(node.val);
            dfs(node.left);
            dfs(node.right);
        }
        
        dfs(root);
        return result;
    }
    
    static deserialize(data) {
        let index = 0;
        
        function build() {
            if (index >= data.length) return null;
            
            const val = data[index++];
            if (val === 'null') return null;
            
            const node = new TreeNode(val);
            node.left = build();
            node.right = build();
            
            return node;
        }
        
        return build();
    }
}

Key Takeaways

1. Traversals Are Unique: Each combination of traversals uniquely defines a binary tree structure
2. Root Identification: Always identify root from appropriate traversal sequence first
3. Subtree Division: Properly divide in-order sequences to identify left and right subtrees
4. Index Mapping: Use hash maps for efficient element location in large trees
5. Edge Cases: Handle empty trees, single nodes, and null values correctly

Tree construction from traversals is fundamental for understanding tree properties, implementing serialization systems, and solving complex algorithmic problems in competitive programming and system design interviews.