Problem

Given the root of a binary tree, write a function to return or print all the leaf nodes of the tree. A leaf node is a node that does not have any children (both left and right are null).

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Input:
Binary Tree:  
       1
      / \
     2   3
        / \
       4   5
 
Output:
Leaf Nodes: [2, 4, 5]

Explanation:
The leaf nodes in the binary tree are the nodes without children. Here, nodes with values `2`, `4`, and `5` are leaf nodes.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Input:
Binary Tree:  
          10
         /  
        20  
       / \
      30   40
 
Output:
Leaf Nodes: [30, 40]

Explanation:
The leaf nodes in the binary tree are nodes with values `30` and `40`, since these nodes have no children.

Solution

Method 1 - DFS

Reasoning or Intuition

  1. Definition of leaf: A node is considered a leaf node if it doesn’t have any children (both left and right are null).
  2. Traversal: To find all leaf nodes, traverse the binary tree, checking every node. If the node meets the leaf node condition, add it to the result.
  3. Traversal methods:
    • Recursive: Efficiently traverse the binary tree using depth-first search (DFS).
    • Iterative: Using a stack, traverse nodes and check for leaves.

Approach

We will use a DFS approach to traverse the binary tree recursively to collect all leaf nodes:

  1. Traverse the binary tree from the root.
  2. For each node, check if it is a leaf node.
  3. If a leaf node is found, add it to the result list.
  4. Continue traversing all children of the current node recursively.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    // Method to collect all leaf nodes
    public List<Integer> getLeafNodes(TreeNode root) {
        List<Integer> leafNodes = new ArrayList<>();
        dfs(root, leafNodes);
        return leafNodes;
    }

    // Helper function to traverse the tree and collect leaf nodes
    private void dfs(TreeNode node, List<Integer> leafNodes) {
        if (node == null) {
            return;
        }

        // Check if the current node is a leaf
        if (node.left == null && node.right == null) {
            leafNodes.add(node.val);
        }

        // Recursively traverse left and right children
        dfs(node.left, leafNodes);
        dfs(node.right, leafNodes);
    }
}

// Examples
public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);

        Solution solution = new Solution();
        System.out.println(solution.getLeafNodes(root));  // Output: [2, 4, 5]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def getLeafNodes(self, root):
        # Helper function to collect leaf nodes
        def dfs(node, leaf_nodes):
            if node is None:
                return
            
            # Check if the current node is a leaf
            if node.left is None and node.right is None:
                leaf_nodes.append(node.val)
            
            # Recursively traverse left and right children
            dfs(node.left, leaf_nodes)
            dfs(node.right, leaf_nodes)

        # List to store the leaf nodes
        leaf_nodes = []
        dfs(root, leaf_nodes)
        return leaf_nodes

# Examples
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.left = TreeNode(4)
root.right.right = TreeNode(5)

solution = Solution()
print(solution.getLeafNodes(root))  # Output: [2, 4, 5]

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the binary tree. Each node is visited exactly once during traversal.
  • 🧺 Space complexity: O(h), where h is the height of the binary tree. This space is used implicitly for the recursion stack.