Skip to content

2196. Create Binary Tree From Descriptions 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
    unordered_map<TreeNode*, TreeNode*> childToParent;
    unordered_map<int, TreeNode*> valToNode;

    for (const vector<int>& d : descriptions) {
      const int p = d[0];
      const int c = d[1];
      const bool isLeft = d[2];
      TreeNode* parent = valToNode.contains(p)
                             ? valToNode[p]
                             : (valToNode[p] = new TreeNode(p));
      TreeNode* child = valToNode.contains(c)
                            ? valToNode[c]
                            : (valToNode[c] = new TreeNode(c));
      childToParent[child] = parent;
      if (isLeft)
        parent->left = child;
      else
        parent->right = child;
    }

    // Pick a random node and traverse upwardly.
    TreeNode* root = childToParent.begin()->second;
    while (childToParent.contains(root))
      root = childToParent[root];
    return root;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public TreeNode createBinaryTree(int[][] descriptions) {
    Map<TreeNode, TreeNode> childToParent = new HashMap<>();
    Map<Integer, TreeNode> valToNode = new HashMap<>();

    for (int[] d : descriptions) {
      final int p = d[0];
      final int c = d[1];
      final int isLeft = d[2];
      TreeNode parent = valToNode.getOrDefault(p, new TreeNode(p));
      TreeNode child = valToNode.getOrDefault(c, new TreeNode(c));
      valToNode.put(p, parent);
      valToNode.put(c, child);
      childToParent.put(child, parent);
      if (isLeft == 1)
        parent.left = child;
      else
        parent.right = child;
    }

    // Pick a random node and traverse upwardly.
    TreeNode root = childToParent.keySet().iterator().next();
    while (childToParent.containsKey(root))
      root = childToParent.get(root);
    return root;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def createBinaryTree(self, descriptions: list[list[int]]) -> TreeNode | None:
    children = set()
    valToNode = {}

    for p, c, isLeft in descriptions:
      parent = valToNode.setdefault(p, TreeNode(p))
      child = valToNode.setdefault(c, TreeNode(c))
      if isLeft:
        parent.left = child
      else:
        parent.right = child
      children.add(c)

    root = (set(valToNode) - set(children)).pop()
    return valToNode[root]