• Root : First topmost node .

• SubTree : any branches of the tree

• parent node: a node with subtree

• child node: subtree of the parent node

• Leaf node: a node at the bottom of the tree , since it has no subtrees ( node with no child).

Example (1): The node representing the university is the parent and a node representing a college is a child. In the same example the IT college is the parent of the CS ,CE and BIS departments.

Example(2):Drives in a harddisk and the folders, subfolders and files.

• Binary Tree: nodes have 2 children at most ,a left and a right child.

Example: Mathematical expression.

The content of a tree can be traversed in 3 different forms to present the expression in infix ,postfix and prefix forms.

• Binary search tree (BST): The left child of any node's key value is less than its parent's , and the right child's is greater than or equal to its parent's.

Example: store data for fast retrieval using binary search tree.

For example , 3 comparisons are needed to locate 'Yousif' in the first figure , but in the second figure  , 7 comparisons are necessary.

• The height of a tree (h) : ( number of nodes -1 ) on the longest path from the root to a leaf.

• Full binary tree : All nodes at level h-1 have 2 children.

• Complete binary tree: Full binary tree up to level h-1 , and the level h is filled from left to right . 

• Balanced tree: The height of any node's right subtree differs from its left subtree by no more than one.

Example : The tree rooted at 'Mariam'  and 'Tariq' are examples of balanced trees. ( See the next figure)

 

Operations on binary search tree:

1. Create a tree ( Constructor)

2. Destroy a tree (Destructor)

3. Attach left and right (insertion)

4. Detach left and right (deletion)

5. Pre- , in - , post- order traversal

6. Set and get node details.

Example:

Search	Looking for Bedoor , we first check the root node , and Since Bedoor is less than 'Maryam' we branch to the left of the tree .Compare with 'Fatima' and branch left again , compare with 'Bader' and branch right to locate 'Bedoor'.
Insertion	Example : We want to insert a record for 'Salma' . Since 'Salma' is greater than 'Maryam' ,less than 'Tariq' and greater than 'Mazin' and Mohammed' , 'Salma' will be on the right of 'Mohammed'.
Deletion	Node being deleted Operation is a leaf node Initialize its parent's pointer that points to the node to be deleted to NULL. has only one child The parent's pointer is reset to point to the child of the node to be deleted whether left or right . has 2 children We have 2 choices: (1) The item whose search key is immediately greater in value than the deleted node's search key (in-order successor)  OR  (2) immediately less than it (in-order predecessor ). These are the left most node of the deleted node's right subtree , and the right most node of its left subtree. These nodes can either be leaf or have one child  and their deletion is easier. In order traversal : Ali , Bader , Bedoor , Fatima , Maisa , Maryam , Mazen , Mohammed , Tariq , Yousif. in-order predecessor : Maisa in-order successor : Mazen
Retrieval	Same search
Traversal	Best done recursively. Preorder(T) if ( T is not empty)    { visit the current node      Preorder(left subtree of T)      Preorder(right subtree of T)  } Inorder(T) if ( T is not empty)    { Inorder(left subtree of T)      visit the current node      Inorder(right subtree of T) } Postorder(T) if ( T is not empty)    { Postorder(left subtree of T)       Postorder(right subtree of T)       visit the current node }

The root is placed in position 1 , then for any element in position i , its left child can be found in position 2i and its right child resides in  2i+1 . The parent can be found at position i/2.