Binary Search Tree

A binary search tree is a binary tree which is either empty or satisfies the following Rules.

1.      The value of the key in the left child or left sub tree is less than the value of the root.

2.      The value of the key in the right child or right sub tree is more than or equal to the value of the root.

3.      All the sun tree of the left and right children observes the two rules. The fig 8.20 shows a typical binary structure observing the above rules. The number 7 is the root node of the binary tree. If has two sub-tree the left sub tree with node 3 and right sub tree with node 9. The value of left sub tree node is lower than the value of the root and the value of the right sub tree node is higher than the value of the root. This attribute is seen in all the down below nodes to the left and right of the root.

The student must understand the different between binary tree and binary search tree. While answering questions, the students are advised to understand whether the question is on binary tree or binary search tree. 

Threaded Binary Trees

In a linked representation of a binary tree, the number of null links (null pointers) are actually more than non-null pointers. Consider the following binary tree.

In the above binary tree there are 7 null pointers (number 6 through 12 and shown with dotted lines) and 5 actual pointers. In all there are 12 pointers. We can generalize it that for any binary tree with n nodes there will be (n+1) null pointers and 2n total pointers. The objective here is to make effective use of these null pointers. A. J. Perlis and C. Thornton jointly proposed an idea to make use of these null pointers. According to this idea we are going to replace all the null pointers by the appropriate pointers values called threads. A binary tree is threaded is threaded according to a particular traversal method. And the null pointer replacement scheme is defined as follows.

If the left link (lchild) of a node p is normally equal to NULL then this link is replaced by a pointer to the node which immediately precedes node p in inorder traversal. And similarly, if the right link (rchild) of a node p is normally equal to NULL then this link is replaced by pointer to its inorder successor node.  

                                                                         D B E A F C

So,

Rchild of D is made to point to B.

Ichild of E is made to point to B.

Rchild of E is made to point to A.

Ichild of F is made to point A.

Rchild of F is made to point C.

Data Structure & Algorithms Assignment Help, Live Experts 

Struggling with data structure problems? Data structure subject is quite tough to learn? Need quick assistance in data structure questions? ExpertsMind.com is right place for you where your search ends, We at ExpertsMind offer online data structure assignment help, data structure homework help and data structure and algorithms question's answers by best online support by qualified tutors.

ExpertsMind.com - Binary Search Tree Assignment Help, Binary Search Tree Homework Help, Binary Search Tree Assignment Tutors, Binary Search Tree Solutions, Binary Search Tree Answers, Binary Trees Assignment Tutors