Print all leaf nodes in a binary tree
Given a binary tree, write a function that returns a list containing all the leaf nodes of the binary tree in the order in which they appear from left to right. In case two leaf nodes are at the same distance from the leftmost node, the one that has a lesser depth has to be printed first.
Remember/Consider:
If both horizontal and vertical distances are the same for two leaf nodes, then print the one with smaller node data.
Input format :
Elements in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 on its place.
For example, the input for the tree depicted in the below image would be :
1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1
Explanation :
Level 1 :
The root node of the tree is 1
Level 2 :
Left child of 1 = 2
Right child of 1 = 3
Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6
Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)
Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)
The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null (-1).
Note :
The above format was just to provide clarity on how the input is formed for a given tree.
The sequence will be put together in a single line separated by a single space. Hence, for the above depicted tree, the input will be given as:
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output Format :
You have to return a list containing all the leaf nodes of the binary tree in the order in which they appear from left to right.
Constraints :
0 <= N <= 10^5
0 <= Value of node <= 10^8
Where 'N' is the total number of nodes in the BinaryTree.
time Limit: 1sec
CodingNinjas
author
2y
Simple easy standard problem. Solved using DFS
CodingNinjas
author
2y
Vertical Order Traversal
We will maintain the horizontal level of each node. The horizontal level of the root node is considered to be zero. Whenever we go to the left child of any node, its horizontal...read more
Help your peers!
Add answer anonymously...
Top AlphaSense Software Developer interview questions & answers
Popular interview questions of Software Developer
Top HR questions asked in AlphaSense Software Developer
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app