Find Leaves of Binary Tree LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple Atlassian Bloomberg eBay Facebook Google LinkedIn MicrosoftViews 4002

Problem Statement

Find Leaves of Binary Tree LeetCode Solution – Given the root of a binary tree, collect a tree’s nodes as if you were doing this:

  • Collect all the leaf nodes.
  • Remove all the leaf nodes.
  • Repeat until the tree is empty.

Example

Test Case 1:

Input:

root = [1, 2, 3, 4, 5]

Output:

[[4, 5, 3], [2], [1]]

Find Leaves of Binary Tree LeetCode Solution

Explanation

[[3, 5, 4], [2], [1]] and [[3, 4, 5], [2], [1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

Approach:

Idea:

  • Collect leaves and updated root from the left subtree.
  • Collect leaves and updated root from the right subtree
  • Accumulate the leaves based on both the results and update the root accordingly using both the result, send the collected leaves and newly updated root higher up in recursion
  • The base condition of the recursion function will be, if the specified root is the leaf, return the list with a single element root.val and updated root as null
  • In the main function, iterate on the root until the root becomes null.

This is a DFS solution. The binary tree is a single-direction tree. To delete it’s children, you need to keep the information of the parent node(to set it’s left or right node to null). So this solution you have two-step:

  1. Find the node which node.left == null && node.right == null.
  2. Tell it’s parents to delete the leaves. In my solution, I use to return a boolean value to tell the parent node whether or not to delete a child node. For other solutions, you can pass the parent with a recursive DFS call.

let the height of the node is the round that we remove the node. (e.g. all the leaves have a height of 0). we can know the height of each node only when we reach the leaf and go back.

Therefore when we go back from the leaf to its parent, we collect leaves and put them into a corresponding list. Note that the height of the parent is equal to the max height of its children + 1.

Code for Find Leaves of Binary Tree

Java Program

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private boolean removeLeaves(TreeNode root, List<Integer> layer) {
        if (root == null) return false;
        if (root.left == null && root.right == null) {
            layer.add(root.val);
            return true;
        }
        if (removeLeaves(root.left, layer)) {
            root.left = null;
        }
        if (removeLeaves(root.right, layer)) {
            root.right = null;
        }
        return false;
    }
    
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        while (root != null) {
            List<Integer> layer = new ArrayList<>();
            if (removeLeaves(root, layer)) {
                root = null;
            }
            res.add(layer);
        }
        return res;
    }
}

C++ Program

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int getLeaves(vector<int>&temp, TreeNode* root){
        if(root == nullptr) return 0;
        int left = getLeaves(temp,root->left);
        int right = getLeaves(temp,root->right);
        if(left == 0 && right == 0){
            temp.push_back(root->val);
            return -1;
        }
        if(left == -1) root->left = nullptr;
        if(right == -1) root->right = nullptr;
        return 1;
    }
    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>>res;
        while(root && (root->left || root->right)){
            vector<int>temp;
            getLeaves(temp,root);
            res.push_back(temp);
        }
        res.push_back({root->val});
        return res;
    }
};

Complexity Analysis for Find Leaves of Binary Tree LeetCode Solution

time complexity: 2N = O(N)

space complexity: O(N)

Translate »