Wednesday, January 20, 2010

Binary Trees in Java

One of the coolest data structures that is both highly efficient and very simple is a Binary Tree. Binary Tree is a data structure where a there will be a node having at most two child nodes.

Lets briefly define the concepts of a binary tree and lets take look at a working Java program in the future posts. Binary Tree has three pointers, one pointing to the left child, one pointing to the right child and one pointer to the parent. These are the terms we use with respect to a binary tree.

  • Root - The uppermost node in a binary tree. The parent node is always null for a root or we can say Root does not have a parent.
  • Child - A child is a sub-node to a parent node. A child can be either a left child or a right child
  • Leaf - A node which does not have any right or left nodes to it.
  • Node - constitutes to an element of a tree which has three pointers one to parent, one to right child and one to left child. And it has a place holder to store the data as well.

There are more jargons available with regard to a binary tree but as of now these terms are sufficient.

One of the most common misunderstanding that many have is to tell the definition of a "Binary search tree" when asked for a "Binary tree". They are not the same!!. Although we can say binary search tree is a form of binary tree with some condition. All Binary search trees are Binary trees and not vice versa!!!!

If asked to write a binary tree structure in Java, the following code would be more than sufficient. Note: This is just a raw structure.
public class BinaryTree{
 class Node {
  Node left;
  Node right;
  Node parent;
  int data;
 private Node root;

More trees to come in the following posts.

No comments: