Binary Search Tree

Hi you all:)
i wanna just talk about binary search tree which is also familiar among most of the software engineers.

BST (Binary Search Tree) has a few simple rules:
- Each node must have a value
- All the left subtree nodes must have values less than the node's value
- All the right subtree nodes must have values greater or equal than the node's value

As you can see, there are not any complexity to understand a search tree work mechanism, but a figure could be mohttp://www.youtube.com/watch?v=t3ASa4jpqgkre illustrative :))

After this introductory definition, and now it is the best time to do some exercises on BST. First of all, lets start with traversals of BST.

1. Inorder Traversal ( Left, Root, Right )
2. Preorder Traversal (Root, Left, Right )
3. Postorder Traversal ( Left, Right, Root )

//recursive inorder traversal
void print_inorder( node_t *root) {
if ( !root ) return;
print_inorder( root->left );
printf( "%d ", root->data );
print_inorder( root->right );
}

But you can convert recursive functions to iterative by using stack. Because, recursive functions use stack to hold parameters, local variables and return values in stack.

//iterative inorder traversal
void print_inorder_iter( node_t *root ) {
stack_t stack;
if ( !root ) return;
initialize( &stack );

do {
while ( root ) {
    Push( &stack, root );
    root = root->left;
}
if ( !isEmpty( &stack ) ) {
    root = Pop( &stack );
    printf("%d ", root->data);
}
root = root->right;
} while ( root || !isEmpty( &stack ) );
}

//recursive preorder traversal
void print_preorder( node_t *root ) {
if ( !root ) return;
printf( "%d ", root->data );
print_preorder( root->left );
print_preorder( root->right );
}

//iterative preorder traversal
void print_inorder_iter( node_t *root ) {
stack_t stack;
if ( !root ) return;
initialize( &stack );

do {
 while ( root ) {
     Push( &stack, root );
     root = root->left;
 }
 if ( !isEmpty( &stack ) ) {
     root = Pop( &stack );
     printf("%d ", root->data);
 }
 root = root->right;
} while ( root || !isEmpty( &stack ) );
}

//recursive postorder traversal
void print_postorder( node_t *root ) {
if ( !root ) return;
print_postorder( root->left );
print_postorder( root->right );
printf( "%d ", root->data );
}

1.) How do you get the node numbers of a Binary Tree ?

//this is also known as size of a tree
int get_node_numbers( node *root ) {
if ( !root ) return 0;
return  1 + get_node_numbers( root->left ) + get_node_numbers( root->right );
}

2.) How do you get the Binary Tree height?

int get_tree_height( node *root ) {
if ( !root ) return -1;
return 1 + max( get_tree_height( root->left ), get_tree_height( root->right ) );
}

3.) Get the sum of all nodes in a Binary Tree.

int get_tree_sum( node *root ) {
if ( !root ) return 0;
return root->data + get_tree_sum( root->left ) + get_tree_sum( root->right );
}

4.) What is the number of leaves in a Binary Tree ?

int get_leaf_number( node *root ) {
if ( !root ) return 0;
if ( !root->left && !root->right ) return 1;
return get_leaf_number( root->left ) + get_leaf_number( root->right );
}

5.) What is the minimum value in a Binary Tree?

int get_minimum_value( node *root ) {
if ( !root ) return 0;

while ( root->left ) {
   root = root->left;
}
return root->data;
}

6.) What is the maximum value in a Binary Tree ?

int get_maximum_value( node *root ) {
if ( !root ) return 0;

while ( root->right ) {
    root = root->right;
}
return root->data;
}

7.) Write a function that tests the binary tree whether it is a BST or not. Now, you must be careful about the maximum value of left subtree must be less than the current node's value and also the minimum of the right subtree must be greater than the current node's value.
Lets discuss about this case in the below:

      12
    /  \
   9   13
  / \
 3  15

If you tests only nodes left and right value, then this tree will surprisingly become a BST which is a really bad situation for a developer :))

if ( root->data > root->left->data && root->data <>right->data ) { ... }
This control is not sufficient to test all cases, so be careful while writing all your test functions and try to consider all cases.

Boolean isBinaryTree( node * root ) {
 if ( !root ) return True;

 if ( root->left != NULL && get_maximum_value( root->left ) > root->data )
     return False;

 if ( root->right != NULL && get_minimum_value( root->right ) <= root->data )
     return False;

 if ( isBinaryTree( root->left ) || !isBinaryTree( root->right ) )
     return False;
 return True;
}

8.) Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Return false if no such path can be found.
For example; for this tree and check path sum: 25

      12
    /  \
   9   13
  / \
 3  15

path1: 12 - 9 - 3 : 24 ( false )
path2: 12 - 9 - 15 : 36 ( false )
path3: 12 - 13 : 25 ( true )

To achieve this problem you will substract all nodes' value while traversiing nodes along a path.

Boolean check_path_sum( node *root, int check_sum ) {
    if ( !root ) {
        return ( check_sum == 0 );
    }
    return ( check_path_sum( root->left, check_sum - root->data) || check_path_sum( root->right, check_sum - root->data) );
}

9.) Give back all nodes in a binary tree to memory, in other words you will free a binary tree. Hint : If you free a parent before childs so how do you access childs adress, as a result of this problem you have to free childs before parent. As you can see, it is easy to see postorder traversal must be used.

void free_tree( node *root ) {
   if ( !root ) return;
   free_tree( root->left );
   free_tree( root->right );
   free( root );
}

10.) Change the roles of the left and right pointers of a node. Mirror a binary tree :)

previous version:

      12
    /  \
   9   13
  / \
 3  15

mirror version:

      12
    /  \
   13   9
  / \
 15  3

void mirror_tree( node *root ) {
   if ( !root ) return;
   mirror_tree( root->left );
   mirror_tree( root->right );

   node *p = root->left;
   root->left = root->right;
   root->right = p;
}

11.) For each node in a binary search tree, create a new duplicate node, and insert the duplicate as the left child of the original node. double a binary tree.

void double_tree( node *root ) {
   node *p;
   if ( !root ) return;
   double_tree( root->left );
   double_tree( root->right );
  
   //take a new node
   p = ( node * )malloc(sizeof(node));
   p->left = NULL;
   p->right = NULL;
   p->data = root->data;
  
   if ( !root->left ) {
       root->left = p;
   }
   else {
       p->left = root->left;
       root->left = p;
   }
}

12.) Get the sum of path numbers from root to each leaves. I have also mentioned how to get the number of leaves in a binary tree. This is exactly equal to the path numbers of a binary tree from root to each leaves :)



13.) Find the number of nodes between two nodes. The value of two nodes are given as first and second. Assume that two nodes are in the same subtree.
First, you will search first value in the BST then search second value in the subtree of first.
For example; BST is given in the follow, first 9 and second is 15.

      12
    /  \
   9   13
  / \
 3  15

First search 9 and then search 15 in the subtree of 9.

    9
  / \
 3  15

node * lookup( node * root, int data ) {
    if ( !root ) return NULL;
    if ( data == root->data ) return root;
    else if ( data < root->data ) return lookup( root->left, data );
    else return lookup( root->right, data );
}

int get_number_between_two_nodes( node * root, int first, int second ) {
    int counter = 0;
    root = lookup( root, first );
    //now, root points to first root     
    if ( root == NULL ) return -1;
    //find the last node
    while ( root ) {
        if ( second < root->data ) {
            counter++;
            root = root->left;
        }
        else if ( second > root->data ) {
            counter++;
            root = root->right;
        }
        else {
            counter--;
            break;
        }
    }
    if ( !root ) return -1;
    if ( first == second ) return 0;
    return counter;
}

14.) Print all paths from root to each leaf.

      12
    /  \
   9   13
  / \
 3  15

void print_array( int array[ ], int length ) {
    int i = 0;
    for ( i = 0; i < length; i++ ) {
        printf( "%d - ", array[ i ] );
    }
    printf( "\n" );
}

void print_paths_rec( node * root, int path[ ], int len ) {
    if ( !root ) return;
    path[ len++ ] = root->data;
    if ( root->left == NULL && root->right == NULL ) {
        print_array( path, len );
    }
    print_paths_rec( root->left, path, len );
    print_paths_rec( root->right, path, len );
}

void print_paths( node *root ) {
    int path[ 1000 ];
    print_paths_rec( root, path, 0 );
}