# BST tree structure conversion – Code

Binary search tree (BST) is binary tree, in which the left subtree contains nodes whose keys are less than the node’s key value, while the right subtree contains nodes whose keys are greater than or equal to the node’s key value. Both subtrees are also binary search trees. We can use recursion to solve many BST problems, such as traversal, flip tree etc. Today we are going to use recursion to for BST tree structure conversion.

Amazon Interview Question (CareerCup):
Given a BST convert it into new Data Structure that satisfies following conditions:
1. every leaf node’s left ptr point to its parent and right ptr points to the next leaf
2. every non leaf node’s left ptr points to its parent and right ptr is NULL
3. return the head and print the new DS
example:
7
/ \
5 9
/ \ \
4 6 10
output:
head->;4->;5->;7
|
->;6->;5->;7
|
->;10->;9-7
with optimal time and space complexity

Approach:
We have to iterate the whole data structure because we want to reorder it completely. There are only 2 possibilities to iterate over tree data: depth-first or width-first – which one better suit our needs? If we take another look on resulting we will notice that the first node in result is the first leaf node in the input. That’s a good sign for depth-first Search. So the approach is to use recursion in DFS.

Java Code:

Output:
4->;5->;7
6->;5->;7
10->;9->;7

O Notation:
Time complexity: O(n)
Space complexity: O(n)

Comments are closed