Algorithmic problems: Leaf-Similar Trees

Another Easy category problem which tests our understanding of tree data structures. With the eight th problem of the December leetcoding challenge https://leetcode.com/problems/leaf-similar-trees/ we can flex our tree traversal techniques.

Problem breakdown

We are given the root pointers of two binary trees. We need to check if both trees contain the same leaf-node sequence. A leaf-node sequence is a sequence we get if we traverse the leaf nodes from left to right. It doesn't matter if we traverse the tree using inOrder , preOrder and postOrder fashion. We will only consider the values in the leaf nodes.

My approach

We need to keep track of two things, the sequence of the leaf nodes that we wish to return and that we only add those node values which are in the leaf nodes. Recall that the leaf nodes don't have either the left or right child, we can leverage this information to come up with a base case for our recursive solution. Notice that since we need to check only the leaf nodes this search is called depth-first-search.

As a rough pseudocode, we will

• maintain a list namely seq, to store the leaf node sequences going from left to right

• choose any of the tree traversal techniques, let's go with pre-order

• the edge case is when the given parent node is empty, in this case, we will return an empty sequence

• the base case of the recursive calls is when the current node does not have any children, we will add the value of that node to our seq

• for the other normal nodes, we will recursively call the function on the left child first and then the right child. This way we can guarantee that the sequence we get will be from left to right

• At last, we need to compare if the two sequences are equal and return True else False otherwise

def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:

        def dfsTraversal(root):
            seq = []
            if not root:
                return []
            if not root.left and not root.right:
                seq.append(root.val)
            seq += dfsTraversal(root.left)
            seq += dfsTraversal(root.right)
            return seq

        return dfsTraversal(root1) == dfsTraversal(root2)

Time and Space complexity

The time complexity is the total time required to traverse the depth of the trees O(d1 + d2) where d1 and d2 are the depths or heights of the given trees. The space complexity is the space required to store the leaf nodes' values, we used two lists to do so, therefore it should the O(n+n) where n is the space occupied by the lists.

I will say it again, trees in the world of the algorithm are weird and a tad unintuitive to understand. Until the next post!