LeetCode Problem 366: Find Leaves of Binary Tree

Naive Approach

The most straightforward approach is to repeatedly identify and remove the leaves from the tree until the tree is empty. In each iteration, we traverse the tree and collect all the leaf nodes. After collecting them, we remove them from the tree. We repeat this process until the root is null. This will modify the original tree.

Algorithm:

1. Initialize an empty list of lists, result, to store the leaves at each level.
2. While the root is not null:
   • Initialize an empty list, leaves, to store the leaves for the current level.
   • Traverse the tree to identify all leaf nodes and add them to the leaves list. A leaf node is a node whose left and right children are both null.
   • Remove the identified leaf nodes from the tree. When a node is a leaf, its parent's left or right pointer should be set to null.
   • Add the leaves list to the result list.
3. Return the result list.

Code (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findLeavesNaive(root):
    result = []
    while root:
        leaves = []
        new_root = removeLeaves(root, leaves)
        result.append(leaves)
        root = new_root
    return result


def removeLeaves(root, leaves):
    if not root:
        return None

    if not root.left and not root.right:
        leaves.append(root.val)
        return None

    root.left = removeLeaves(root.left, leaves)
    root.right = removeLeaves(root.right, leaves)

    return root

Time Complexity: O(N^2) in the worst case, where N is the number of nodes. Removing each leaf takes O(N) and this process is repeated until the tree is empty. In the worst case (e.g. a skewed tree) each removal operation takes O(N).

Space Complexity: O(N) due to the recursion stack. It could be O(log N) for balanced tree. O(N) to store the result in the worst case.

Optimal Approach

The optimal approach leverages the height of each node in the tree. The key idea is that leaves are nodes with height 0. The root of the tree will be the last to be removed, so it will have the maximum height. The height can be defined recursively.

Algorithm:

1. Initialize an empty list of lists, result, to store the leaves at each level.
2. Define a recursive function getHeight(node) that does the following:
   • If the node is null, return -1. (Important: -1 as null node has height -1.)
   • Recursively calculate the height of the left and right subtrees.
   • The height of the current node is the maximum of the heights of its left and right subtrees, plus 1.
   • If the result list does not have an element at the index corresponding to the height of the current node, add a new empty list to result.
   • Append the value of the current node to the list at the index corresponding to its height in the result list.
   • Return the height of the current node.
3. Call the getHeight(root) function.
4. Return the result list.

Code (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findLeaves(root):
    result = []

    def getHeight(node):
        if not node:
            return -1

        left_height = getHeight(node.left)
        right_height = getHeight(node.right)
        height = max(left_height, right_height) + 1

        if len(result) <= height:
            result.append([])

        result[height].append(node.val)
        return height

    getHeight(root)
    return result

Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.

Space Complexity: O(N), where N is the number of nodes in the tree. This is due to the recursion stack in the worst-case scenario (skewed tree). The result list can also store up to N node values in the worst case.

Edge Cases

• Empty tree: If the input tree is empty (root is null), the algorithm should return an empty list.
• Single node tree: If the tree consists of only one node, the algorithm should return a list containing a list with the value of that single node.
• Skewed tree: The algorithm should handle skewed trees (where all nodes are either left or right children) efficiently. The optimal solution's O(N) time complexity makes it suitable for such cases.