CODEWITHSUNDEEP
algorithmrecursionbinary-search-tree
Moria
Moria

Reputation: 125

Algorithm to construct a binary search tree out of elements from another bst

I'm trying to come up with an algorithm to construct a binary search tree using the elements from another binary search tree, but with the restriction that those elements have to be greater or equal than some given integer, let's call it x.

I thought of a recursive approach (using in order traversal):

binary_tree (bst tree, int x) {
  if (tree is empty)
    return empty;
  if (tree->element>=x)
    insert tree->element in a new BST;
  else ????
}

I have no idea what the last recursive call would be, I obviously can't write two returns like this:

else
  return (tree->left, x)
  return (tree->right, x)

And I can't think of anything else, sorry if this is a silly question! I'm just starting with recursion and it's really confusing.

Upvotes: 2

Views: 307

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59144

It's a little tricky to do this recursively, because there isn't a 1-1 correspondence between subtrees in the tree you have and subtrees in the tree you want.

The simplest way to do this is to copy the values >= x into a list in order, and then build a tree from the list recursively.

Upvotes: 0

Mitch
Mitch

Reputation: 3418

Lets think about what we are doing here. We want to construct a tree from an existing binary search tree. Because the existing tree is a BST we get some helpful info.

For any node V, if V <= x then the subtree pointed to by V -> left will have nodes all smaller than x. So we no longer need to look in the left subtree anymore. However if we hit a node that is greater than or equal to x we need to continue the recursion. Lets bring this all together in pseudo code 

newBST(root):
    if root is null 
        return 
    if root.val >= x
        addNewNode(root.val)
        newBST(root.right)
        newBST(root.left)
    else:
        newBST(root.right)

Upvotes: 1

Related Questions