0

Binary and Binary Search Tree – Best Guide

Trees are used to impose a hierarchical structure on a collection of data items.

Here is complete Guide on Binary and Binary Search Trees.

• This is a tree because it is a set of nodes {A,B,C,D,E,F,G,H,I}, with node A as a root node and the remaining nodes partitioned into three disjointed sets {B,G,H,I}, { C,E,F} and {D}, respectively.
• Each of these sets is a tree because each satisfies the aforementioned definition properly.

• Even though this is a set of nodes {A,B,C,D,E,F,G,H,I}, with node A as a root node, this is not a tree because the fact that node E is shared makes it impossible to partition nodes B through I into disjointed sets.

Degree of a Node of a Tree

• The degree of a node of a tree is the number of subtrees having this node as a root. In other words, the degree is the number of descendants of a node. If the degree is zero, it is called a terminal or leaf node of a tree.

Degree of a Tree

• The degree of a tree is defined as the maximum of degree of the nodes of the tree, that is, degree of tree = max (degree(node i) for I = 1 to n)

Level of a Node

• We define the level of the node by taking the level of the root node as 1, and incrementing it by 1 as we move from the root towards the subtrees. So the level of all the descendants of the root nodes will be 2. The level of their descendants will be 3, and so on. We then define the depth of the tree to be the maximum value of the level of the node of the tree.

Binary Tree

• A binary tree is a finite set of nodes that is either empty or it consists of a root and two disjoint binary trees called the left sub tree and the right sub tree.

• A binary tree is a rooted tree in which every node has at most two children. A full binary tree is a tree in which every node has zero or two children. Also known as a proper binary tree. A perfect binary tree is a full binary tree in which all leaves (vertices with zero children) are at the same depth (distance from the root, also called height).

• 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.

Binary Search Tree

• A binary search tree is a binary tree in which the data in the nodes are 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. For numbers this can obviously be done. For strings, alphabetical ordering is often used. For records of data, a comparison based on a particular field (the key field) is often used.

Binary Search Tree Example

Binary Search Tree In Data Structure

• A binary tree is a type of data structure for storing data such as numbers in an organized way.
• Binary search trees allow binary search for fast lookup, addition and removal of data items, and can be used to implement dynamic sets and lookup tables.
• The order of nodes in a BST means that each comparison skips about half of the remaining tree, so the whole lookup takes time proportional to the binary logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables. Several variants of the binary search tree have been studied.

Binary Search Tree Algorithm

If root == NULL 
    return NULL;
If number == root->data 
    return root->data;
If number < root->data 
    return search(root->left)
If number > root->data 
    return search(root->right)

Binary Search Tree Search Algorithm

Step 1: IF ROOT -> DATA = ITEM OR ROOT = NULL
    Return ROOT
   ELSE
   IF ROOT < ROOT -> DATA
   Return search(ROOT -> LEFT, ITEM)
  ELSE
   Return search(ROOT -> RIGHT,ITEM)
  [END OF IF]
  [END OF IF]
Step 2: END

Reference:

• Programiz.com
• Javatpoint.com