Given a binary tree, the task is to print left and right leaf nodes separately.
Examples:
Input:
0
/ \
1 2
/ \
3 4
Output:
Left Leaf Nodes: 3
Right Leaf Nodes: 4 2
Input:
0
\
1
\
2
\
3
Output:
Left Leaf Nodes: None
Right Leaf Nodes: 3
Approach:
- Check if given node is null. If null, then return from the function.
- For each traversal at right and left, send information about the child (left or right child) using the parameter type. Set type = 0 while descending to the left branch and set type = 1 for the right branch.
- Check if it is a leaf node. If the node is a leaf node, then store the leaf node in one of the two vectors of left and right child.
- If node is not a leaf node continue traversal.
- In the case of a single node tree, it will be both a root and a leaf node. This case has to be handled separately.
Below is the implementation of the above approach:
C++
// C++ program for the// above approach#include <bits/stdc++.h>using namespace std;// Structure for// Binary Tree Nodestruct Node { int data; Node* left; Node* right; Node(int x) : data(x) , left(NULL) , right(NULL) { }};// Function for// dfs traversalvoid dfs(Node* root, int type, vector<int>& left_leaf, vector<int>& right_leaf){ // If node is // null, return if (!root) { return; } // If tree consists // of a single node if (!root->left && !root->right) { if (type == -1) { cout << "Tree consists of a single node\n"; } else if (type == 0) { left_leaf.push_back(root->data); } else { right_leaf.push_back(root->data); } return; } // If left child exists, // traverse and set type to 0 if (root->left) { dfs(root->left, 0, left_leaf, right_leaf); } // If right child exists, // traverse and set type to 1 if (root->right) { dfs(root->right, 1, left_leaf, right_leaf); }}// Function to print// the solutionvoid print(vector<int>& left_leaf, vector<int>& right_leaf){ if (left_leaf.size() == 0 && right_leaf.size() == 0) return; // Printing left leaf nodes cout << "Left leaf nodes\n"; for (int x : left_leaf) { cout << x << " "; } cout << '\n'; // Printing right leaf nodes cout << "Right leaf nodes\n"; for (int x : right_leaf) { cout << x << " "; } cout << '\n';}// Driver codeint main(){ Node* root = new Node(0); root->left = new Node(1); root->right = new Node(2); root->left->left = new Node(3); root->left->right = new Node(4); vector<int> left_leaf, right_leaf; dfs(root, -1, left_leaf, right_leaf); print(left_leaf, right_leaf); return 0;} |
Java
// Java program for the// above approachimport java.util.*;class GFG { // Structure for // Binary Tree Node static class Node { int data; Node left; Node right; public Node(int data) { this.data = data; this.left = null; this.right = null; } }; // Function for // dfs traversal static void dfs(Node root, int type, Vector<Integer> left_leaf, Vector<Integer> right_leaf) { // If node is // null, return if (root == null) { return; } // If tree consists // of a single node if (root.left == null && root.right == null) { if (type == -1) { System.out.print("Tree consists of a single node\n"); } else if (type == 0) { left_leaf.add(root.data); } else { right_leaf.add(root.data); } return; } // If left child exists, // traverse and set type to 0 if (root.left != null) { dfs(root.left, 0, left_leaf, right_leaf); } // If right child exists, // traverse and set type to 1 if (root.right != null) { dfs(root.right, 1, left_leaf, right_leaf); } } // Function to print // the solution static void print(Vector<Integer> left_leaf, Vector<Integer> right_leaf) { if (left_leaf.size() == 0 && right_leaf.size() == 0) return; // Printing left leaf nodes System.out.print("Left leaf nodes\n"); for (int x : left_leaf) { System.out.print(x + " "); } System.out.println(); // Printing right leaf nodes System.out.print("Right leaf nodes\n"); for (int x : right_leaf) { System.out.print(x + " "); } System.out.println(); } // Driver code public static void main(String[] args) { Node root = new Node(0); root.left = new Node(1); root.right = new Node(2); root.left.left = new Node(3); root.left.right = new Node(4); Vector<Integer> left_leaf = new Vector<Integer>(), right_leaf = new Vector<Integer>(); dfs(root, -1, left_leaf, right_leaf); print(left_leaf, right_leaf); }}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 program for the# above approach # Structure for# Binary Tree Nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None # Function for # dfs traversaldef dfs(root, type_t, left_leaf, right_leaf): # If node is # null, return if (not root): return # If tree consists # of a single node if (not root.left and not root.right): if (type_t == -1): print("Tree consists of a single node") elif (type_t == 0): left_leaf.append(root.data) else: right_leaf.append(root.data) return # If left child exists, # traverse and set type_t to 0 if (root.left): dfs(root.left, 0, left_leaf, right_leaf) # If right child exists, # traverse and set type_t to 1 if (root.right): dfs(root.right, 1, left_leaf, right_leaf) # Function to print# the solutiondef prints(left_leaf, right_leaf): if (len(left_leaf) == 0 and len(right_leaf) == 0): return # Printing left leaf nodes print("Left leaf nodes") for x in left_leaf: print(x, end = ' ') print() # Printing right leaf nodes print("Right leaf nodes") for x in right_leaf: print(x, end = ' ') print() # Driver codeif __name__=='__main__': root = Node(0) root.left = Node(1) root.right = Node(2) root.left.left = Node(3) root.left.right = Node(4) left_leaf = [] right_leaf = [] dfs(root, -1, left_leaf, right_leaf) prints(left_leaf, right_leaf) # This code is contributed by pratham76 |
C#
// C# program for the// above approachusing System;using System.Collections.Generic;class GFG { // Structure for // Binary Tree Node public class Node { public int data; public Node left; public Node right; public Node(int data) { this.data = data; this.left = null; this.right = null; } }; // Function for // dfs traversal static void dfs(Node root, int type, List<int> left_leaf, List<int> right_leaf) { // If node is // null, return if (root == null) { return; } // If tree consists // of a single node if (root.left == null && root.right == null) { if (type == -1) { Console.Write("Tree consists of a single node\n"); } else if (type == 0) { left_leaf.Add(root.data); } else { right_leaf.Add(root.data); } return; } // If left child exists, // traverse and set type to 0 if (root.left != null) { dfs(root.left, 0, left_leaf, right_leaf); } // If right child exists, // traverse and set type to 1 if (root.right != null) { dfs(root.right, 1, left_leaf, right_leaf); } } // Function to print // the solution static void print(List<int> left_leaf, List<int> right_leaf) { if (left_leaf.Count == 0 && right_leaf.Count == 0) return; // Printing left leaf nodes Console.Write("Left leaf nodes\n"); foreach (int x in left_leaf) { Console.Write(x + " "); } Console.WriteLine(); // Printing right leaf nodes Console.Write("Right leaf nodes\n"); foreach (int x in right_leaf) { Console.Write(x + " "); } Console.WriteLine(); } // Driver code public static void Main(String[] args) { Node root = new Node(0); root.left = new Node(1); root.right = new Node(2); root.left.left = new Node(3); root.left.right = new Node(4); List<int> left_leaf = new List<int>(), right_leaf = new List<int>(); dfs(root, -1, left_leaf, right_leaf); print(left_leaf, right_leaf); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript program for the// above approach// Structure for// Binary Tree Nodeclass Node { constructor(data) { this.data = data; this.left = null; this.right = null; }};// Function for// dfs traversalfunction dfs(root, type, left_leaf, right_leaf) { // If node is // null, return if (root == null) { return; } // If tree consists // of a single node if (root.left == null && root.right == null) { if (type == -1) { document.write("Tree consists of a single node<br>"); } else if (type == 0) { left_leaf.push(root.data); } else { right_leaf.push(root.data); } return; } // If left child exists, // traverse and set type to 0 if (root.left != null) { dfs(root.left, 0, left_leaf, right_leaf); } // If right child exists, // traverse and set type to 1 if (root.right != null) { dfs(root.right, 1, left_leaf, right_leaf); }}// Function to print// the solutionfunction print(left_leaf, right_leaf) { if (left_leaf.Count == 0 && right_leaf.Count == 0) return; // Printing left leaf nodes document.write("Left leaf nodes<br>"); for(var x of left_leaf) { document.write(x + " "); } document.write("<br>"); // Printing right leaf nodes document.write("Right leaf nodes<br>"); for(var x of right_leaf) { document.write(x + " "); } document.write("<br>");}// Driver codevar root = new Node(0);root.left = new Node(1);root.right = new Node(2);root.left.left = new Node(3);root.left.right = new Node(4);var left_leaf = [];var right_leaf = [];dfs(root, -1, left_leaf, right_leaf);print(left_leaf, right_leaf);</script> |
Output:
Left leaf nodes 3 Right leaf nodes 4 2
Time complexity: O(h) where h is height of 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!
