Binary Search Tree

Introduction to Tree
Tree is used in data structure. A tree is used for quick search and can store unordered data.

A tree diagram is a useful tool to list all the logical possibilities of a sequence of events where each event can occur in a finite number of ways.

A tree consists of a root, a number of branches leaving the root, and possible additional branches leaving the end points of other branches.
A tree is normally constructed from left to right. A vertex of degree 1 in a tree is called a terminal vertex or a leaf node and a vertex of degree greater than 1 in a tree is called an internal vertex or a branch. The nodes at the lowest levels of the tree (the ones with no sub-trees) are called leaves.

Mathematical Definition of Tree: A tree is a set of finite number of elements that are either empty or partitioned into three disjoint subsets. First subset contains a single element called node. The other subsets are themselves tree, left and right sub-tree. Each element is called node of the tree. Both the sub-trees are themselves binary trees.

Simple definition of Tree: A graph is a tree, if there is a unique path between any two of its vertices.

Given vertices v and w, if v lies on the unique path between w and the root, then v is an ancestor of w and w is a descendant of v.

To use trees in counting problems, we use a branch to represent each possible choice. The possible outcomes are represented by the leaves (end points of branches).

Introduction to Binary Tree
A binary tree is a rooted tree in which every internal vertex has at most two children. Every child in a binary tree is designated either a left child or a right child (but not both).

Here, v is right child of u.

A full binary tree is a binary tree in which each internal vertex has exactly two children.

Binary Trees in Computer Science: Binary trees are specially used in computer science to represent algebraic expression with Arbitrary nesting of balanced parentheses.

The above figure represents the expression a/b. Here the operator (/) is the root and b are the left and right children.

The second figure represents the expression a/(c+d). Here the operator (/) is the root. Here the terminal vertices are variables (here a, c and d), and the internal vertices are arithmetic operators (+ and /).

Like this, for a/(b-c.d) is:

Explanation
A binary tree is similar to a tree, but not quite the same. For a binary tree, each node can have zero, one, or two children. In addition, each child node is clearly identified as either the left child or the right child. Thus there is a definite left-right ordering of the child nodes. Even when a node has only one child, that child must be identified as either the left child or the right child. Note that a child drawn to the left of its parent is meant to be the left child and that a child drawn to the right of its parent is meant to be the right child.
Maximum number of leaves in a level can be determined by the formula.

This forms a complete tree, whose height is defined as the number of links from the root to the deepest leaf.

Binary Search Tree
A binary search tree is a binary tree in which the data in the nodes is ordered in a particular way. To be precise, starting at any given node, the data in any nodes of its left sub-tree must all be less than the item in the given node, and the data in any nodes of its right sub-tree must be greater than or equal to the data in the given node.

The following is a binary search tree where each node contains a person's name. Only first names are used in order to keep the example simple. Note that the names are ordered alphabetically so that DAVE comes before DAWN; DAVID comes before DAWN but after DAVE, etc .

By starting with an empty binary search tree and adding the data items one by one. The first item becomes the root. The next item is placed in either a left child or right child node, depending on the ordering. The third item is compared to the root, we go left or right depending on the result of the comparison, etc. until we find the spot for it. In each case we follow a path from the root to the spot where we insert the new item, comparing the new item to each item in the nodes encountered along the way, going left or right at each node.  

Traversals of Binary Tree

There are many ways to traversal, to travel throughout, a binary tree. Three of them are discussed below. The outline of discussing traversals includes three steps.



Example using these traversals to explain above table

Example

• Build a binary search tree for the words banana, peach, apple, pear, coconut, mango, and papaya using alphabetical order.

• Build a binary search tree for the words oenlolgy, phrenology, campanology, ornithology, ichthyology, limnology, alchemy, and astrology using alphabetical order.

Key Terms:
Root Node:     Node at the top of a tree - the one from which all operations on the tree commence.

Leaf Node:     Node at the bottom of a tree - farthest from the root. Leaf nodes have no children.

Level:     The level of a vertex is the number of edges along the unique path between it and the root.

Branch:     A branch is a sequence of nodes such that the first is the parent of the second, the second is the parent of the third, etc. The length of a branch is the number of line segments traversed (which is one less than the number of nodes).

Height:     Number of nodes which must be traversed from the root to reach a lowest leaf of a tree.

Sibling:     Two vertices that are both children of the same parent are called siblings.


For code implementation in object oriented see : Binary Search Tree - Code
Feel free to comment with your questions and suggestions regarding the post content...!