2196.create-binary-tree-from-descriptions.md

2196. Create Binary Tree From Descriptions

Hash Table

• We use hash table to store value to new created node mapping.
• Then we can link the child node to the parent node by using the isLeft flag.
• Find the root: Identify the root as the node that never appears as a child.

Or we can use in-degree to find the root.

fun createBinaryTree(descriptions: Array<IntArray>): TreeNode? {
    val map = HashMap<Int, TreeNode>()
    val hasParent = HashSet<Int>()
    for ((p, c, isLeft) in descriptions) {
        if (p !in map) map[p] = TreeNode(p)
        if (c !in map) map[c] = TreeNode(c)

        val parent = map[p]!!
        val child = map[c]!!
        if (isLeft == 1) {
            parent.left = child
        } else {
            parent.right = child
        }
        hasParent.add(c)
    }
    for ((p, _, _) in descriptions) {
        if (p !in hasParent) return map[p]
    }
    return null
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Graph

We can build the tree by using graph modeling approach.

descriptions = [
    [20, 50, 1],
    [20, 17, 0],
    [50, 30, 1],
]

graph[20] = {(50, 1), (17, 0)}
graph[50] = {(30, 1)}

Find root = 20
build(20)
    build(50)
        build(30)
    build(17)

     20
   /    \
  50    17
 /
30

fun createBinaryTree(descriptions: Array<IntArray>): TreeNode? {
    val childSet = HashSet<Int>()
    val graph = HashMap<Int, HashSet<IntArray>>()
    for (d in descriptions) {
        val (parent, child, isLeft) = d
        if (parent !in graph) graph[parent] = HashSet<IntArray>()
        graph[parent]!!.add(d)
        childSet.add(child)
    }
    // find parent
    var rootValue: Int? = null
    for (parent in graph.keys) {
        if (parent !in childSet) {
            rootValue = parent
            break
        }
    }
    return if (rootValue != null) {
        build(rootValue, graph)
    } else {
        null
    }
}

private fun build(value: Int, graph: HashMap<Int, HashSet<IntArray>>): TreeNode? {
    val root = TreeNode(value)
    graph[value]?.forEach { (parent, child, isLeft) ->
        val childNode = build(child, graph)
        if (isLeft == 1) {
            root.left = childNode
        } else {
            root.right = childNode
        }
    }
    return root
}

• Time Complexity: O(n), the time complexity in general graph is O(V + E), in this problem, V is number of unique nodes, E is number of descriptions which is n.
  • For binary tree, each node has at most two children, so V <= 2 * E.
  • Build the graph: O(E) = O(n)
  • Find the root: O(V) = O(n)
  • Traverse the graph: O(V + E) = O(n + n) = O(n)
• Space Complexity: O(n).