# BinarySearch Tree implementation & traversals

I am practicing various tree algorithms and that require code review for it's efficiency, clarity and also if it can be made better etc.

Is there a better way to call parent.findMin(parent)

TreeNode.java

package binarytree;

public class TreeNode
{
TreeNode left;
TreeNode right;
int data;
TreeNode parent;
int size=0;

TreeNode(int data)
{
this.data = data;
size = 1;
}

int size()
{
return size;
}

void setLeftChild(TreeNode left)
{
this.left = left;
if(left == null)
{
left.parent = this;
}
}

void setRightChild(TreeNode right)
{
this.right = right;
if(right == null)
{
right.parent =  this;
}
}

void insertInOrder(int d)
{
if(d <= data)
{
if(left == null)
{
setLeftChild(new TreeNode(d));
}
else
{
left.insertInOrder(d);
}
}
else{
if(right == null)
{
setRightChild(new TreeNode(d));
}
else{
right.insertInOrder(d);
}
}
size++;
}

void postOrderTraversal(TreeNode parent)
{
if(parent == null) return;

postOrderTraversal(parent.left);
postOrderTraversal(parent.right);
printVal(parent);
}

void preOrderTraversal(TreeNode parent)
{
if(parent == null) return;

printVal(parent);
preOrderTraversal(parent.left);
preOrderTraversal(parent.right);
}

void inOrderTraversal(TreeNode parent)
{
if(parent == null) return;

inOrderTraversal(parent.left);
printVal(parent);
inOrderTraversal(parent.right);
}

void printVal(TreeNode parent)
{
System.out.print(parent.data + "\t");
}

/* binary tree find Minimum */
int findMin(TreeNode parent)
{
if(parent == null) return 0;

int min = parent.data;
if(parent.left !=null)
{
min = Math.min(min, findMin(parent.left));
}

if(parent.right != null)
{
min = Math.min(min, findMin(parent.right));
}

return min;
}

/* binary tree find Maximum */
int findMax(TreeNode parent)
{
if(parent == null) return 0;

int max = parent.data;
if(parent.left !=null)
{
max = Math.max(max, findMax(parent.left));
}
if(parent.right != null)
{
max = Math.max(max, findMax(parent.right));
}
return max;
}
}


Traversal.java

package binarytree;

import binarytree.TreeNode;
public class Traversals {

public static void main(String[] args)
{
TreeNode parent = new TreeNode(1);
TreeNode left = new TreeNode(2);
TreeNode right = new TreeNode(3);
TreeNode next = new TreeNode(5);

parent.insertInOrder(left.data);
parent.insertInOrder(right.data);
parent.insertInOrder(next.data);

System.out.println("Pre-order traversal");
parent.preOrderTraversal(parent);
System.out.println();

System.out.println("Post-order traversal");
parent.postOrderTraversal(parent);
System.out.println();

System.out.println("In-order traversal");
parent.inOrderTraversal(parent);
System.out.println();

System.out.println("min element:"+parent.findMin(parent));
System.out.println("max element:"+parent.findMax(parent));
}

}

-

Here are a few things you can do to improve this:

• You don't specify visibility of your methods or variables. Presumably you want your variables to be private, but I'm not sure which of your methods you want public or not. I imagine you don't want setLeftChild or setRightChild to be public since you can't enforce your ordering constraints if anyone can just change children when they feel like it.
• Both setLeftChild and setRightChild will throw NullPointerExceptions when passed a null value. You want != instead of == in your check.
• Do your nodes need references to their parents?
• In your Traversals class you have nodes named parent, but you are actually referring to the root node of your tree. I would rename that.
• You don't need to create the other three TreeNode classes since you only use them to get the value that you passed into them when you call insertInOrder. Just call insertInOrder with the values you want.
• You shouldn't pass in the parent parameter to your traversal methods. These are instance methods and can just refer to the member variables directly.
• Initialize size once. Currently you set it to 0 and then 1.
• I'm assuming you have plans to use size later on. Otherwise you can just remove it entirely.
-
You don't need to create the other three TreeNode... how would I do it otherwise? – fscore May 1 '14 at 23:17
parent.insertInOrder(2), parent.insertInOrder(3), parent.insertInOrder(5). – Cameron May 1 '14 at 23:21

Rethink findMax. The way you constructed the tree, a maximal value is never in the left subtree. Similarly, if there is a right subtree, the maximal value is always there.

-
true but can u give a example? – fscore May 1 '14 at 23:23
can u suggest a better way to call parent.findMin(parent) – fscore May 1 '14 at 23:24
findMax: follow right branch as long as possible. Return the leaf value. findMin: same, but follow left branch. Neither needs to be recursive. – vnp May 1 '14 at 23:54