Two nodes of a binary search tree have been incorrectly swapped. How will you efficiently restore the tree to its correct state?

An inorder traversal of BST will be in sorted order.

In the incorrect BST  2 of the nodes are swapped .

use this to your advantage and find these 2 elements in inorder traversal which violate the sorted order.This 2 elements need to  be swapped.Thats it!!

Just modify inorder traversal function as follows

[gist https://gist.github.com/vishnujayvel/5879942 ]

Printing nodes at the K distance from root of a binary Tree

Here is a recursive solution.The code is self explanatory

[gist https://gist.github.com/vishnujayvel/5871650]

Printing nodes at the K distance from root of a binary Tree

Here is a recursive solution.The code is self explanatory

[gist https://gist.github.com/vishnujayvel/5871650]

Inorder traversal of BST without recursion

We all know how easy it is to print bst in inorder traversal using recursion.

What if we want to do this without recursion?

Its not difficult.Recursion uses stacks implicitly while executing.So lets use stacks itself.

algorithm:

1) keep on traversing the root left pushing each node into the stack.

2)if stack is empty exit the function

3)When reaching end pop an element and print it and make root=root->right .Goto step1

	void nonRecursiveInorderTraversal(node *root){
	stack<node*> s;
	cout<<endl;
	while(1){
	while(root){
	s.push(root);
	root=root->left;
	}
	if(s.empty())
	break;
	root=s.top();
	s.pop();
	cout<<root->data<<" ";
	root=root->right;
	}
	}

view raw

inorder

hosted with ❤ by GitHub

Binary Search Tree in Java

import java.util.Scanner;

/**
*
* @author vishnu
*/
class Node
{

Node left;
Node right;
int value;

public Node(int value) {
this.value = value;
}
}
class BinarySearchTree{

Node root;
public BinarySearchTree(){
root=null;

}
void insertNode(int value){
insert(root,value);
System.out.println(“inserting!!!!”+value+” “+root.value);
}
void insert(Node root, int value) {
if(this.root==null){

this.root=new Node(value);

return;
}
if (value < root.value) {
if (root.left != null) {
insert(root.left, value);
} else {
root.left = new Node(value);
System.out.println(“inserted!!!!”+value);

}
} else if (value > root.value) {
if (root.right != null) {
insert(root.right, value);
} else {
root.right = new Node(value);
System.out.println(“inserted!!!!”+value);
}
}
}

void inOrder(){
inOrder(root);
}

void inOrder(Node node) {
if (node != null) {
inOrder(node.left);
System.out.println( node.value);
inOrder(node.right);
}
}

}

public class BST {

public static void main(String[] args)

{

BinarySearchTree tree = new BinarySearchTree();
Node rootnode = null;
Scanner S=new Scanner(System.in);
int c,n;
while(true){
System.out.println(“menu:\n1)Insert\n2)Display\n3)Exit”);
c=S.nextInt();
switch(c){
case 1:
System.out.println(“enter the value”);
n=S.nextInt();
tree.insertNode(n);
break;
case 2:

System.out.println(“Traversing tree in order”);
tree.inOrder();
break;
case 3:
System.exit(0);
break;

}

}

}

}