Leaf Nodes from Preorder of BST

Moderate

0/80

Average time to solve is 25m

3 upvotes

Asked in companies

Problem statement

You are given a ‘root’ of a Binary Search Tree in preorder fashion, and your task is to print all the leaf nodes in the tree. A leaf node is a node whose left and right pointer point to NULL.

More formally, you have to print all the leaf nodes from left to right, i.e., they should be sorted.

Note:

A binary search tree, also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

Example

For Example, the root node is given as follows :
‘ROOT’ = 6 4 3 -1 -1 5 -1 -1 8 7 -1 -1 9 -1 -1

Level 1 :
The root node of the tree is 6

Level 2 :
Left child of 6 = 4
Right child of 6 = 8

Level 3 :
Left child of 4 = 3
Right child of 4 = 5
Left child of 8 = 7
Right child of 8 = 9

Therefore all the leaf nodes are 3, 5, 7 and 9.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains a single integer ‘T,’ representing the number of test cases or queries to be run. 

The line of each test case contains elements in the pre-order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

Pre-order input refers to giving input in Node, left child, and then the right child and the recur for the same.

Output Format :

For every test case, print a single line that contains all the leaf nodes of the given Binary Search Tree.

The output of each test case is printed in a separate line.

Note:

You don’t have to print anything. It has already been taken care of. Just implement the function.

Constraints:

1 <= ‘T’ <= 10
1 <= ‘N’ <= 1000
0 <= data <= 10^3

Time Limit: 1 sec

Sample Input 1:

2
6 4 3 -1 -1 5 -1 -1 8 7 -1 -1 9 -1 -1 
3 1 0 -1 -1 2 -1 -1 5 4 -1 -1 6 -1 -1

Sample Output 1:

3 5 7 9
0 2 4 6

Explanation of the Sample Input 1:

For the first test case, 
Level 1 :
The root node of the tree is 6

Level 2 :
Left child of 6 = 4
Right child of 6 = 8

Level 3 :
Left child of 4 = 3
Right child of 4 = 5
Left child of 8 = 7
Right child of 8 = 9
The leaf nodes of the given binary tree from left to right are 3, 5, 7, and 9.

For the second test case,
Level 1 :
The root node of the tree is 3

Level 2 :
Left child of 3 = 1
Right child of 3 = 5

Level 3 :
Left child of 1 = 0
Right child of 1 = 2
Left child of 5 = 4
Right child of 5 = 6
The leaf nodes of the given binary tree from left to right are 0, 2, 4, and 6.

Sample Input 2:

2
10 9 -1 -1 11 -1 -1 
9 -1 10 -1 11 -1 12 -1 -1

Sample Output 2:

9 11
12

Hint 1

Will Preorder traversal help?

Approaches (1)

Approach 1

Preorder Traversal

The idea is to traverse the given tree in a preorder fashion, and if we encounter a node whose ‘left,’ and ‘right’ pointer is ‘NULL,’ then we add that node to the resultant vector/array.

The steps are as follows:

We will use a helper function to traverse the tree in a preorder fashion.
‘helper’ takes the ‘root’ and ‘res’ array to store nodes as input parameters.
If the current nodes left and right pointer are NULL, add the node to ‘res.’
Return ‘res’ as the final result.

Time Complexity

O(N), where ‘N’ is the number of nodes in the binary tree.

We are traversing the whole binary once. Hence, the overall time complexity is O(N).

Space Complexity

O(N), where ‘N’ is the number of nodes in the binary tree.

We are traversing the whole binary once. Hence, the overall recursive stack made will be equal to the height of the tree. Hence space complexity is O(N).

(100% EXP penalty)

Leaf Nodes from Preorder of BST

Console