Print leaf nodes from preorder of a BST

Approach

The Naive Approach for this problem can be to find the inorder of the array provided to you. Now, traverse the preorder array and while traversing, find each element in the inorder array using Binary Search. We can use Binary Search here because inorder traversal of the Binary Search Tree is always sorted. If the element from both arrays match, we print it as a leaf node.

This approach is very simple. Still, we don’t use it because the time complexity is O(n log n), which is not acceptable. 

Optimum approach

The Optimum Approach for this problem will use the Stack and Binary Search Tree properties.

We will traverse the preorder array using two pointers, x=0 and y=1. It is implied that the preorder traversal starts from the root to the leftmost node. By each passing value, we compare two consecutive nodes. The preorder will be in the decreasing order first. After decreasing order ends, you will get a node greater than the previous node. This node will be pushed onto the stack. Whenever we get a value greater than the peek of the stack, we pop an element. The popped element will be printed as a leaf node.

Algorithm

Now, when you know every aspect of this problem, have a look at the algorithm given below.

1. Set two pointers, say x and y, at index 0 and 1, respectively.
2. Traverse the pointers through the preorder array at two consecutive indices.
3. If arr[x] > arr[y], arr[x] will be pushed to stack.
4. Else arr[y] > top of element, pop an element.
5. Print all the elements popped.

Implementation in Java

import java.util.*;
class Main
{
    public static void main(String[] args)
    {
        int pre[] = {5, 2, 1, 3, 4, 7, 6, 8, 9};
        int len = pre.length;
        Node(pre, len);
    }
    
    static void Node(int pre[], int len)
    {
        Stack<Integer> stack = new Stack<Integer> ();
        for (int x = 0, y = 1; y < len; x++, y++)
        {
            boolean search = false;
 
            if (pre[x] > pre[y])
                stack.push(pre[x]);
 
            else
            {
                while (!stack.isEmpty())
                {
                    if (pre[y] > stack.peek())
                    {
                        stack.pop();
                        search = true;
                    }
                else
                    break;
                }
            }
 
            if (search)
                System.out.print(pre[x] + " ");
        }
        System.out.println(pre[len - 1]);
    }
}

Input: 

5, 2, 1, 3, 4, 7, 6, 8, 9

Output: 

1, 4, 6, 9

Complexity Analysis
 

🍉 Time Complexity
In the implementation above, the pointer may have to traverse all the nodes before finding the required node. Therefore, in this case, the time complexity will be O(n).

🍉 Space Complexity
Since the space scales 1:1 with changes to the size of n, that is n increases by 1 every time a new iteration is performed. Therefore, the space complexity would be O(n).

Implementation using Recursion

We have used a simple recursive approach here. The concept is to use two variables for minimum and maximum values. We will recursively create a root node and check if that node has a child or not using two boolean variables. If the root node created has no child nodes, both the boolean variables return false. It will be printed as a leaf node.

import java.util.*;
class Main
{
    static int a = 0;
    public static void main(String[] args)
    {
        int pre[] = {5, 2, 1, 3, 4, 7, 6, 8, 9};
        int len = pre.length;
        print(pre, len);
    }
    
    static boolean Leaf(int pre[], int len, int minimum, int maximum)
    {
        if (a >= len)
        {
            return false;
        }
        if (pre[a] > minimum && pre[a] < maximum)
        {
            a++;
            boolean left = Leaf(pre, len, minimum, pre[a - 1]);
            boolean right = Leaf(pre, len, pre[a - 1], maximum);
            if (!left && !right)
            {
                System.out.print(pre[a - 1] + " ");
            }
            return true;
        }
        return false;
    }
    static void print(int pre[], int len)
    {
        Leaf(pre, len, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
}

Complexity Analysis
 

🍉 Time Complexity
In the implementation above, the pointer will traverse only the required nodes using recursion. Therefore, in this case, the time complexity will be O(log n).

🍉 Space Complexity
Since the space scales 1:1 with changes to the size of n, that is n increases by 1 every time a new iteration is performed. Therefore, the space complexity would be O(n).

Frequently Asked Questions

Mention the properties of tree data structure that are used while solving problems.

Some properties of tree data structure which we use while solving problems are mentioned below.

• Number of Edges
• Depth of a node
• Height of a node
• Height of the tree
• Degree of a node

What is a Threaded Binary Tree?

Such a tree in which all right child pointers would be null and pointing towards the inorder successor of the node is known as a threaded binary tree. Similarly, all left child pointers would also be null and pointing towards the inorder predecessor of the node.

What are the advantages of using the Threaded Binary Tree data structure?

A few advantages of using Threaded Binary Tree data structure are:

• Traversal becomes much faster.
• No stack overhead would occur.
• Every node becomes accessible.
• Easy implementation of insertion and deletion.

Conclusion

To summarize the article, we looked at the problem statement, looked at every possible condition that could occur, understood the approach, went through the Pseudocode, saw the implementation, tested the code against an example output, and did time and space complexities analysis.

We hope the above discussion helped you understand and solve the problem better.

This will also help you learn how to approach any problem like this in the future.

For coders who want to solve more such questions, refer to the list below.

• Predecessor and Successor in BST
• BST Iterator
• Size of the largest BST in Binary Tree
• LCA of two nodes in a BST

Enroll in our courses, go for mock tests, solve problems available, and interview puzzles. Also, you can focus on interview stuff- interview experiences and an interview bundle for placement preparations. Do upvote our blog to help other ninjas grow.

Happy Coding!