Binary Search Tree from Descriptions

Create a binary tree from descriptions.

The full problem statement can be found on leetcode.

The descriptions are provided as an array arrays, where each element has three items:

• In the 0 position: The value of the parent node.
• In the 1 position: The value of the node.
• In the 2 position: If the node is to the left or right of its parent.

All nodes in the tree have unique values.

Analysis

There are probably a few different ways to do this, I decided to start with a more straightforward solution and then see if I could cook up something better.

Initial Algorithm

First, the nodes are constructed without any linkages and saved in a hash by their value alongside their respective instruction. Then these values are iterated through - each node uses its description to be linked with its parent.

Since the root node is not given an instruction but only referred to in index 0 and since the root is unique, when the hash of nodes does not contain a value it is certain that the value is that of the root node.

Another Algorithm

Two hashes are created. Every node is saved into the first hash using its color, any node whose parent is not known is saved into the second hash in a subhash where it is indexed by is_left, using its parents color.

The current node is then inspected for any matching entries in the second hash that need a parent with its value. If this is found then the links are created and the entry is removed from the second hash.

Solutions

All of these solutions have linear time complexity, as they all have one recursion over descriptions.

Initial Solution

My initial solution performed reasonably, but was not ideal. It placed in the \(59\%\) quantile for runtime and the \(52\%\) quantile for memory. This is okay, but not great. The solution is presented bellow:

class SolutionInitial:
    def createBinaryTree(
        self,
        descriptions: list[list[int]],
    ) -> Optional[TreeNode]:

        # NOTE: Works because is tree of unique values.
        nodes = {
            color: (TreeNode(color), (color_parent, color, is_left))
            for color_parent, color, is_left in descriptions
        }

        # NOTE: Linking step. Root should only appear as a parent, and thus
        #       was not constructed in the definition of nodes.
        root = None
        for node, (color_parent, _, is_left) in nodes.values():
            if color_parent not in nodes:
                if root is None:
                    root = TreeNode(color_parent)
                node_parent = root
            else:
                node_parent, _ = nodes[color_parent]

            if is_left:
                node_parent.left = node
            else:
                node_parent.right = node

        return root

The apparent reason for this slowness is that there are two loops of approximately the size of the descriptions input.

Another Solution

My second solution performed worse in runtime at the \(40\%\) quantile but excellently in memory in the \(98\%\) quantile.

class SolutionInitial:
    def createBinaryTree(
        self,
        descriptions: list[list[int]],
    ) -> Optional[TreeNode]:

        # NOTE: Works because is tree of unique values.
        nodes = {
            color: (TreeNode(color), (color_parent, color, is_left))
            for color_parent, color, is_left in descriptions
        }

        # NOTE: Linking step. Root should only appear as a parent, and thus
        #       was not constructed in the definition of nodes.
        root = None
        for node, (color_parent, _, is_left) in nodes.values():
            if color_parent not in nodes:
                if root is None:
                    root = TreeNode(color_parent)
                node_parent = root
            else:
                node_parent, _ = nodes[color_parent]

            if is_left:
                node_parent.left = node
            else:
                node_parent.right = node

        return root

The speed trade-off is likely the result of all of the logic in the loop.

Yet Another Solution

I decided to take a look at some other solutions and saw that some created both nodes when neither existed. It turns out that this solution was about as good as the above - I was very confused as the spoiler solution ranked very well. Then I changed one thing, the unpacking of desc in the for loop statement, which I moved into the body. The following is said solution, it ranked \(92\%\) in runtime and \(70\%\) in memory.

class Solution:
    def createBinaryTree(
        self,
        descriptions: list[list[int]],
    ) -> Optional[TreeNode]:

        # NOTE: Works because is tree of unique values.
        nodes = {}
        children = set()
        for desc in descriptions:
            color_parent, color, is_left = desc
            if color not in nodes:
                node = TreeNode(color)
                nodes[color] = node
            else:
                node = nodes[color]

            # NOTE: Create parent node if not exists.
            if color_parent not in nodes:
                node_parent = TreeNode(color_parent)
                nodes[color_parent] = node_parent
            else:
                node_parent = nodes[color_parent]

            # NOTE: Assign.
            if is_left:
                node_parent.left = node
            else:
                node_parent.right = node

            children.add(color)

        # There will only be one left.
        for value in nodes:
            if value not in children:
                return nodes[value]

        return None