Construct Binary Tree from Parent Array

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Build binary tree from parent array where parent[i] = parent of node i (-1 for root).

Algorithm

1Create all nodes. For each i: if parent[i] == -1: root = i. Else: attach i as left or right child of parent[i].

Common Pitfalls

•Create nodes first, then link. Root has parent = -1.

Construct Binary Tree from Parent Array.java

Java

// Approach: Build nodes array first, then set parent-child relationships using the parent array.
// Time: O(n) Space: O(n)
import java.util.*;

class Node {
    int data;
    Node left, right;

    Node(int key) {
        data = key;
        left = right = null;
    }
}

class Solution {
    // Function to construct binary tree from parent array.
    public Node createTree(int parent[]) {

        HashMap<Integer, Node> map = new HashMap<>();
        for (int i = -1; i < parent.length; i++)
            map.put(i, new Node(i));

        for (int i = 0; i < parent.length; i++) {
            Node parentNode = map.get(parent[i]);
            Node childNode = map.get(i);

            if (parentNode.left == null)
                parentNode.left = childNode;
            else
                parentNode.right = childNode;
        }

        return map.get(-1).left;
    }
}

Was this solution helpful?