Binary Tree-definition, characteristics, implementation and operations

A binary tree is a hierarchical data structure unlike linear data structures like stacks,queues,linked lists, arrays etc. Data representation is by nodes.

Characteristics of binary trees.

1.Data representation is by nodes

2.A binary tree has one root only. The root is the entry point to the tree.

3.There can be at most two children per node (child nodes).

4.A binary tree can have a root without children.

5.It’s not a must for child nodes to have children in which case the are called leaf nodes.

6.There can only be one path of traversal from the root node to any other node.

7.We can have an empty tree-no root, no children.

8.Nodes are connected by edges and direction of the edges is unidirectional from parent to child.

9.Tree height is the longest path from root to the furthest leaf node.

Some physical presentations of binary trees as per above characteristics

1.Binary tree with root only

2.Empty binary Tree (has no root)

3.Binary tree with root and child nodes

*The above tree has root node with value 70.

*Each node has at most two (2) children.

*Some nodes have 1 child e.g. 60

*Some nodes have no children (leaf nodes)e.g. 58,68,80,85

*Each node has exactly one path to it from the root .e.g. to get to 68,the path is 70 ->65 -> 68.

*The above tree has a height of 4

4.Binary tree with root and child nodes

*The above is a valid binary tree with root containing value 70.Root has 2 children ,65 and 82.

*So long as the characteristics of a binary tree are met, the shape of the tree does not matter.

5.Invalid binary tree

*The above tree is invalid since there is more than one path from root (70) to child 82 i.e. 70 -> 82 and 70->65->82.

Binary tree implementation.

As discussed, a binary tree is made up of nodes. The nodes need to be interconnected to form the hierarchy of the tree. In order to establish the network, each node keeps pointers to two nodes, its children i.e. the left and right children.

Sample java code demonstrating a node is as shown below.

package btree;

public class Node {

    int val;

    Node left;

    Node right;

    public Node(int val) {

        this.val = val;

    }

}

Using above Node class,the tree hierarchy can be created by creating pointers as in below code

Node _70 = new Node(70);

        Node _65 = new Node(65);

        Node _82 = new Node(82);

        Node _60 = new Node(60);

        Node _68 = new Node(68);

        Node _58 = new Node(58);

        Node _80 = new Node(80);

        Node _85 = new Node(85);

        _70.left = _65;

        _70.right = _82;

        _65.right = _68;

        _65.left = _60;

        _60.left = _58;

        _82.left = _80;

        _82.right = _85;

The above code created a tree with structure as in example 3.(binary tree with root and child nodes)

Binary tree operations

The following are operations on a binary tree.

1.Insertion- creating the hierarchy structure by adding nodes.

2.Traversal-travelling the tree and processing each node. There are two modes of traversing a binary tree that will be discussed in another tutorial.

Depth First Search-traversal by going deep into one path before visiting the next path.
Breadth First Search/ Level order traversal -traversal by exploring all nodes at current depth before moving the nodes at the next depth level.

3.Deletion-removing of a node(s) in the structure. Done by updating pointers of the parent of the child to be deleted.

On this Page