LeetCode Entry

2196. Create Binary Tree From Descriptions

15.07.2024 medium 2024 kotlin rust

Restore binary tree from [parent, child, isLeft]

2196. Create Binary Tree From Descriptions medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/671

Problem TLDR

Restore binary tree from [parent, child, isLeft] #medium

Intuition

Use the HashMap. Remember which nodes are children.

Approach

• Kotlin: getOrPut
• Rust: entry.or_insert_with. Rc cloning is cheap.

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

    fun createBinaryTree(descriptions: Array<IntArray>): TreeNode? {
        val valToNode = mutableMapOf<Int, TreeNode>()
        val children = mutableSetOf<Int>()
        for ((parent, child, isLeft) in descriptions) {
            val pNode = valToNode.getOrPut(parent) { TreeNode(parent) }
            val cNode = valToNode.getOrPut(child) { TreeNode(child) }
            if (isLeft > 0) pNode.left = cNode else pNode.right = cNode
            children += child
        }
        return valToNode.entries.find { it.key !in children }?.value
    }

    pub fn create_binary_tree(descriptions: Vec<Vec<i32>>) -> Option<Rc<RefCell<TreeNode>>> {
        let mut map = HashMap::new(); let mut set = HashSet::new();
        let mut get = |v| { map.entry(v).or_insert_with(|| Rc::new(RefCell::new(TreeNode::new(v)))).clone() };
        for d in descriptions {
            let child = get(d[1]);
            let mut parent = get(d[0]); let mut parent = parent.borrow_mut();
            set.insert(d[1]);
            *(if d[2] > 0 { &mut parent.left } else { &mut parent.right }) = Some(child)
        }
        map.into_values().find(|v| !set.contains(&v.borrow().val))
    }