⚡Flashcard Drill➔
NeetCode #416LC-2196MediumTrees
← Back to All Problems

#416 · #2196 · Create Binary Tree From Descriptions(根据描述创建二叉树)

📌 Problem Statement & Constraints

You are given a 2D array descriptions where descriptions[i] = [parent, child, isLeft] describes a binary tree edge. Return the root of the reconstructed tree. All node values are unique and the input describes a valid binary tree. Constraints: 1 <= descriptions.length <= 10^4, 1 <= parent, child <= 10^5.

💡 Core Algorithmic Approaches

  1. Create or reuse a node for every value mentioned, then link each child to its parent on the correct side.
  2. The root is the only value that never appears as a child.
  3. A dictionary from value to node makes the create-or-reuse step O(1).
  4. Then scan for the value absent from the children set.

💻 Benchmark Python3 Implementation

class Solution:
    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
        nodes = {}
        children = set()
        for p, c, is_left in descriptions:
            if p not in nodes:
                nodes[p] = TreeNode(p)
            if c not in nodes:
                nodes[c] = TreeNode(c)
            if is_left:
                nodes[p].left = nodes[c]
            else:
                nodes[p].right = nodes[c]
            children.add(c)
        for v, node in nodes.items():
            if v not in children:          # never a child -> the root
                return node
        return None

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass to build, one to find the root.
💾 Space Complexity
O(n) for the node map and the children set.

⚠️ Interview Pitfalls & Follow-ups

  • Creating a new node for every mention: a value can appear as both a parent and a child, so the map must be checked first.
  • Assuming the descriptions are topologically ordered: they are not; a child may be described before its parent.
  • Swapping left and right: isLeft == 1 means left, 0 means right.
  • Looking for the root by value ordering: the root is identified structurally (never a child), not by value.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems