Popular Posts

Saturday, February 4, 2012

Construct a Binary search tree

If you are given a number N, build a binary search tree of size N with node values from 1 to N.

public class BuildTree {

public Node getTree(int n) {
if (n <= 0) {
System.out
.println("Asking for constructing a tree of size zero or negative number.");
return null;
}
return buildTree(1, n);
}

public Node buildTree(int left, int right) {
if (left > right)
return null;

int rootValue = (int) Math.floor((left + right) / 2);
Node node = new Node(rootValue);
node.left = buildTree(left, rootValue - 1);
node.right = buildTree(rootValue + 1, right);
return node;
}

public static class Node {

public int value;
// member variables will be initialized to null by default.
public Node left;
public Node right;

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

public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}

No comments:

Post a Comment