Page 254 - DCAP407_DATA_STRUCTURE

Unit 13: Binary Search Trees

In this example:
1. The variable count is a global variable and it is initialized to zero. It is also
declared static so that it retains its value in consecutive function calls.

2. A structure named node is created. It consists of two pointer variables
named L and R that point to the left node and right node.
3. An object called NODE is created to access the structure element.
4. The function count_leaf is defined which accepts a parameter root of type
NODE.
5. If root is not NULL, then the leaf nodes in the left sub-tree of the root is
counted by the function. If a node has no left and right child, then the
variable count is incremented.
6. Then, the leaf nodes in the right sub-tree of the root is counted by the
function.

Which of the following are binary search trees? Justify your answers.

Write a C program to implement a binary search tree.

13.2 Summary

• Search trees are data structures that support many dynamic-set operations such as searching,
finding the minimum or maximum value, inserting, or deleting a value.
• In a binary search tree, for a given node n, each node to the left has a value lesser than n and each
node to the right has a value greater than n.
• The time taken to perform operations on a binary search tree is directly proportional to the height
of the tree.
13.3 Keywords

Degenerate Trees: Unbalanced trees.
Dynamic Sets: Dynamic sets are data structures that support operations such as search, insert, delete,
minimum, maximum, successor and predecessor.
Inorder Successor: In binary tree, inorder successor of a node is the next node in inorder traversal of the
binary tree. Inorder successor is null for the last node in inorder traversal.
Ordered List: An ordered list is a list that is maintained in some predefined order such as, alphabetical
or numerical order.

LOVELY PROFESSIONAL UNIVERSITY 247