Find Leaves of Binary Tree

Find Leaves of Binary Tree is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Postorder Traversal subpattern.

Problem statement

You are given the root of a binary tree. Repeatedly remove all leaf nodes (nodes with no children) from the tree, and collect the values of these nodes in a list for each round of removal. Continue this process until the tree is empty. Return a list of lists, where each inner list contains the values of the leaves removed at each round, in the order they were removed.

Constraints: - The number of nodes in the tree is in the range [1, 100]. - Each node's value is a unique integer.

Return the list of lists of node values, where each inner list represents the leaves removed in each round.

Topics and companies

Topics: Tree, Depth-First Search, Binary Tree.

Reported in interviews at LinkedIn, Amazon.

How to practise Find Leaves of Binary Tree on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N), where N is the number of nodes in the tree. Each node is visited exactly once. time and O(N), for the result vector and the recursion stack in the worst case (skewed tree). space.

Open Find Leaves of Binary Tree in the code editor, or read the Find Leaves of Binary Tree editorial for a worked solution with its approach and complexity analysis.

Where Find Leaves of Binary Tree sits in the DSA pattern sheet

• Tree Traversal Patterns (DFS & BFS) pattern guide
• Recursive Postorder Traversal subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Find Leaves of Binary Tree

Other problems that use the same Recursive Postorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:

• All Nodes Distance K in Binary Tree — Medium, same subpattern
• Balanced Binary Tree — Easy, same subpattern
• Binary Tree Maximum Path Sum — Hard, same subpattern
• Binary Tree Postorder Traversal — Easy, same subpattern
• Delete Nodes And Return Forest — Medium, same subpattern
• Diameter of Binary Tree — Easy, same subpattern