Leaf Nodes from Preorder of a Binary Search Tree Using Python

What is a Binary Search Tree?

A binary tree is a binary data structure containing different nodes in which each node has at most two child nodes. These nodes follow some properties, including:

• The left nodes of the binary tree have a lesser value than the root node.
• The right nodes of the binary tree have a larger value than the root node.
• All the sub-nodes must follow the above properties.

There are different ways by which we can traverse the binary search trees:

1. Inorder
2. Preorder
3. Postorder

Inorder Algorithm:

• Left Subtree
• Root Node
• Right Subtree

Preorder Algorithm:

• Root Node
• Left Subtree
• Right Subtree

Postorder Algorithm:

• Left Subtree
• Right Subtree
• Root Node

Problem Statement

We have a preorder of a binary search tree. We need to print the lead nodes from the given preorder of the binary search tree. There can be any number of leaf nodes in the binary search tree.

Consider that all the node values are positive and are already preordered. We have to print the leaf nodes from the tree.

Let's understand this problem with a few examples.

Example 1:

Input:

Output:

70 149 388

Explanation:

The given Binary Search tree is:

The first element will be the root, as in preorder traversal; we first traverse the root node, then the left subtree, and then the right subtree. The elements greater than the root nodes are the elements in the left subtree, and the rest are in the right subtree. After making the binary search tree using this input, we get the elements [70, 149, 388] as the leaf nodes.

Example 2:

Input:

{ 42, 30, 27, 23, 19, 22, 26, 29, 15, 32, 31, 35, 38 }

Output:

15 22 26 29 31 38

Explanation:

The first element will be the root, as in preorder traversal; we first traverse the root node, then the left subtree, and then the right subtree. After making the binary search tree using this input, we get the elements [15, 22, 26, 29, 31, 38] are the leaf nodes.

There are two ways to find the leaf nodes from the preorder of the binary search tree.

1. Simple Method

In this, we will first find the preorder of the binary search tree using both inorder and preorder arrays. We first iterate the preorder array and then find the element for the inorder array.

Code:

Output:

The Leaf Nodes present in the binary search tree are: 
15 22 26 29 31 38 

Explanation:

Firstly, we will iterate the array to find the element in the inorder array. We have used binary search as it gives traversal in ascending order. We have set the range to find the element as [L, R]. If the value of L is equal to R, we get the leaf nodes. Now, we will start with the values of L = 0 and R = node - 1 for the root node of the preorder array. To search the element of the left subtree, we set the value of L = 0 and R = root index. We set L = root index + 1 and R = node -1 for the right subtree.

2. Using Stack

We will use a stack and traverse the array using two pointers.

Code:

Output:

The Leaf Nodes present in the binary search tree are: 
54 78 44

Explanation:

In this, we have used two pointers, i and j. At the start, the value of i = 0 and j = 1. On comparing array[i] and array[j], if array[i] > array[j], it means array[j] is on the left side of a[i]. Then, a[i] will be pushed into the stack. We will now pop the elements till array[i] > top element of the stack and then print the jth value. The jth value will be the leaf nodes of the binary search tree.