Given a binary tree. First print all leaf nodes, after that remove all the leaf nodes from the tree and now print all the new formed leaf nodes and keep doing this until all the nodes are removed from the tree.
Examples :
Input :
8
/ \
3 10
/ \ / \
1 6 14 4
/ \
7 13
Output :
4 6 7 13 14
1 10
3
8
Source :Flipkart On Campus Recruitment
Approach : The idea is to perform simple dfs and assign different values to each node on the basis of following conditions:
- Initially assign all the nodes with value as 0.
- Now, Assign all the nodes with the value as (maximum value of both child)+1.
Tree before DFS: A temporary value zero is assigned to all of the nodes.
Tree after DFS: Nodes are assigned with the value as (maximum value of both child)+1.
Now, you can see in the above tree that after all the values are assigned to each node, the task now reduces to print the tree on the basis of increasing order of node values assigned to them.
Below is the implementation of above approach:
C++
// C++ program to print the nodes of binary// tree as they become the leaf node#include <bits/stdc++.h>using namespace std;// Binary tree nodestruct Node { int data; int order; struct Node* left; struct Node* right;};// Utility function to allocate a new nodestruct Node* newNode(int data, int order){ struct Node* node = new Node; node->data = data; node->order = order; node->left = NULL; node->right = NULL; return (node);}// Function for postorder traversal of tree and// assigning values to nodesvoid Postorder(struct Node* node, vector<pair<int, int> >& v){ if (node == NULL) return; /* first recur on left child */ Postorder(node->left, v); /* now recur on right child */ Postorder(node->right, v); // If current node is leaf node, it's order will be 1 if (node->right == NULL && node->left == NULL) { node->order = 1; // make pair of assigned value and tree value v.push_back(make_pair(node->order, node->data)); } else { // otherwise, the order will be: // max(left_child_order, right_child_order) + 1 node->order = max((node->left)->order, (node->right)->order) + 1; // make pair of assigned value and tree value v.push_back(make_pair(node->order, node->data)); }}// Function to print leaf nodes in// the given ordervoid printLeafNodes(int n, vector<pair<int, int> >& v){ // Sort the vector in increasing order of // assigned node values sort(v.begin(), v.end()); for (int i = 0; i < n; i++) { if (v[i].first == v[i + 1].first) cout << v[i].second << " "; else cout << v[i].second << "\n"; }}// Driver Codeint main(){ struct Node* root = newNode(8, 0); root->left = newNode(3, 0); root->right = newNode(10, 0); root->left->left = newNode(1, 0); root->left->right = newNode(6, 0); root->right->left = newNode(14, 0); root->right->right = newNode(4, 0); root->left->left->left = newNode(7, 0); root->left->left->right = newNode(13, 0); int n = 9; vector<pair<int, int> > v; Postorder(root, v); printLeafNodes(n, v); return 0;} |
Java
// Java program to print the nodes of binary// tree as they become the leaf nodeimport java.util.*;class GFG{// Binary tree nodestatic class Node{ int data; int order; Node left; Node right;};static class Pair{ int first,second; Pair(int a,int b) { first = a; second = b; }}// Utility function to allocate a new nodestatic Node newNode(int data, int order){ Node node = new Node(); node.data = data; node.order = order; node.left = null; node.right = null; return (node);}static Vector<Pair> v = new Vector<Pair>();// Function for postorder traversal of tree and// assigning values to nodesstatic void Postorder(Node node){ if (node == null) return; /* first recur on left child */ Postorder(node.left); /* now recur on right child */ Postorder(node.right); // If current node is leaf node, it's order will be 1 if (node.right == null && node.left == null) { node.order = 1; // make pair of assigned value and tree value v.add(new Pair(node.order, node.data)); } else { // otherwise, the order will be: // max(left_child_order, right_child_order) + 1 node.order = Math.max((node.left).order, (node.right).order) + 1; // make pair of assigned value and tree value v.add(new Pair(node.order, node.data)); }}static class Sort implements Comparator<Pair> { // Used for sorting in ascending order of // roll number public int compare(Pair a, Pair b) { if(a.first != b.first) return (a.first - b.first); else return (a.second-b.second); } }// Function to print leaf nodes in// the given orderstatic void printLeafNodes(int n){ // Sort the vector in increasing order of // assigned node values Collections.sort(v,new Sort()); for (int i = 0; i < v.size(); i++) { if (i != v.size()-1 && v.get(i).first == v.get(i + 1).first) System.out.print( v.get(i).second + " "); else System.out.print( v.get(i).second + "\n"); }}// Driver Codepublic static void main(String args[]){ Node root = newNode(8, 0); root.left = newNode(3, 0); root.right = newNode(10, 0); root.left.left = newNode(1, 0); root.left.right = newNode(6, 0); root.right.left = newNode(14, 0); root.right.right = newNode(4, 0); root.left.left.left = newNode(7, 0); root.left.left.right = newNode(13, 0); int n = 9; Postorder(root); printLeafNodes(n);}}// This code is contributed by Arnab Kundu |
Python3
# Python3 program to print the nodes of binary# tree as they become the leaf node# Binary tree node class newNode: def __init__(self, data,order): self.data = data self.order=order self.left = None self.right = None# Function for postorder traversal of tree and# assigning values to nodesdef Postorder(node,v): if (node == None): return """ first recur on left child """ Postorder(node.left, v) """ now recur on right child """ Postorder(node.right, v) # If current node is leaf node, # it's order will be 1 if (node.right == None and node.left == None): node.order = 1 # make pair of assigned value and tree value v[0].append([node.order, node.data]) else: # otherwise, the order will be: # max(left_child_order, right_child_order) + 1 node.order = max((node.left).order, (node.right).order) + 1 # make pair of assigned value and tree value v[0].append([node.order, node.data]) # Function to print leaf nodes in# the given orderdef printLeafNodes(n, v): # Sort the vector in increasing order of # assigned node values v=sorted(v[0]) for i in range(n - 1): if (v[i][0]== v[i + 1][0]): print(v[i][1], end = " ") else: print(v[i][1]) if (v[-1][0]== v[-2][0]): print(v[-1][1], end = " ") else: print(v[-1][1]) # Driver Coderoot = newNode(8, 0)root.left = newNode(3, 0)root.right = newNode(10, 0)root.left.left = newNode(1, 0)root.left.right = newNode(6, 0)root.right.left = newNode(14, 0)root.right.right = newNode(4, 0)root.left.left.left = newNode(7, 0)root.left.left.right = newNode(13, 0)n = 9v = [[] for i in range(1)]Postorder(root, v)printLeafNodes(n, v)# This code is contributed by SHUBHAMSINGH10 |
C#
// C# program to print the nodes of binary// tree as they become the leaf nodeusing System;using System.Collections.Generic;class GFG{// Binary tree nodepublic class Node{ public int data; public int order; public Node left; public Node right;};public class Pair{ public int first,second; public Pair(int a,int b) { first = a; second = b; }}// Utility function to allocate a new nodestatic Node newNode(int data, int order){ Node node = new Node(); node.data = data; node.order = order; node.left = null; node.right = null; return (node);}static List<Pair> v = new List<Pair>();// Function for postorder traversal of // tree and assigning values to nodesstatic void Postorder(Node node){ if (node == null) return; /* first recur on left child */ Postorder(node.left); /* now recur on right child */ Postorder(node.right); // If current node is leaf node, // it's order will be 1 if (node.right == null && node.left == null) { node.order = 1; // make pair of assigned value // and tree value v.Add(new Pair(node.order, node.data)); } else { // otherwise, the order will be: // Max(left_child_order, // right_child_order) + 1 node.order = Math.Max((node.left).order, (node.right).order) + 1; // make pair of assigned value // and tree value v.Add(new Pair(node.order, node.data)); }}// Used for sorting in ascending order // of roll number public static int compare(Pair a, Pair b) { if(a.first != b.first) return (a.first - b.first); else return (a.second - b.second);} // Function to print leaf nodes in// the given orderstatic void printLeafNodes(int n){ // Sort the List in increasing order // of assigned node values v.Sort(compare); for (int i = 0; i < v.Count; i++) { if (i != v.Count - 1 && v[i].first == v[i + 1].first) Console.Write(v[i].second + " "); else Console.Write(v[i].second + "\n"); }}// Driver Codepublic static void Main(String[] args){ Node root = newNode(8, 0); root.left = newNode(3, 0); root.right = newNode(10, 0); root.left.left = newNode(1, 0); root.left.right = newNode(6, 0); root.right.left = newNode(14, 0); root.right.right = newNode(4, 0); root.left.left.left = newNode(7, 0); root.left.left.right = newNode(13, 0); int n = 9; Postorder(root); printLeafNodes(n);}}// This code is contributed// by Arnab Kundu |
Javascript
<script>// Javascript program to print the nodes of binary// tree as they become the leaf nodeclass Node{ constructor() { this.data = 0; this.order = 0; this.left = this.right = null; }}class Pair{ constructor(a, b) { this.first = a; this.second = b; }}// Utility function to allocate a new nodefunction newNode(data,order){ let node = new Node(); node.data = data; node.order = order; node.left = null; node.right = null; return (node);}let v = [];// Function for postorder traversal of tree and// assigning values to nodesfunction Postorder(node){ if (node == null) return; /* first recur on left child */ Postorder(node.left); /* now recur on right child */ Postorder(node.right); // If current node is leaf node, it's order will be 1 if (node.right == null && node.left == null) { node.order = 1; // make pair of assigned value and tree value v.push(new Pair(node.order, node.data)); } else { // otherwise, the order will be: // max(left_child_order, right_child_order) + 1 node.order = Math.max((node.left).order, (node.right).order) + 1; // make pair of assigned value and tree value v.push(new Pair(node.order, node.data)); }}// Function to print leaf nodes in// the given orderfunction printLeafNodes(n){ // Sort the vector in increasing order of // assigned node values v.sort(function(a,b){ if(a.first != b.first) return (a.first - b.first); else return (a.second-b.second);}) for (let i = 0; i < v.length; i++) { if (i != v.length-1 && v[i].first == v[i+1].first) document.write( v[i].second + " "); else document.write( v[i].second + "<br>"); }}// Driver Codelet root = newNode(8, 0);root.left = newNode(3, 0);root.right = newNode(10, 0);root.left.left = newNode(1, 0);root.left.right = newNode(6, 0);root.right.left = newNode(14, 0);root.right.right = newNode(4, 0);root.left.left.left = newNode(7, 0);root.left.left.right = newNode(13, 0);let n = 9;Postorder(root);printLeafNodes(n);// This code is contributed by avanitrachhadiya2155</script> |
Output
4 6 7 13 14 1 10 3 8
Complexity Analysis:
- Time Complexity : O(nlogn)
- Auxiliary Space : O(n), where n is the number of nodes in the given Binary Tree.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
