Question

I need a way to change the Binary tree to Binary Search tree without using extra space. Could anyone suggest the algorithm

Answer 1

A binary search tree is a type of binary tree.

In a binary search tree, a left child must always have a value less than its parent. A right child must always have a value greater than its parent.

Do you need the method to create a binary search tree?

Answer 2

yes

Answer 3

if( value == nodeValue )
panic();
else if( value < nodeValue)
{
if( leftPointer )
goLeft;
else
makeNewNode( rightPointer );
}
else
{
if( rightPointer )
goRight;
else
makeNewNode( rightPointer );
}

The real fun of binary trees is keeping them (relatively) balanced.

Answer 4

I know all these, But the thing is what I need is, given a Binary tree , should convert the same to Binary Search Tree

Answer 5

Easiest way, and only costs a pointer, would be to traverse the BT, and move the nodes into the BST.