Trees



Pass Quiz and Get a Badge of Learning



Content "filtered", Please subscribe for FULL access.


Chapter 6 : Trees


Tree arrow_upward


  • Trees are flexible, powerful non-linear data structure that can be used to represent data items which has hierarchical relationship.
  • Tree is an ideal data structure for representing hierarchical data.
  • Tree can be defined as a finite set of one or more data items (i.e. nodes) such that:
    • There is a special node called the root of the tree.
    • The remaining nodes are partitioned into n disjointed set of nodes each of which is a subtree.

    Tree Terminologies arrow_upward


    Node:

  • A node is a structure which may contain a value, a condition, or represent a separate data structure.
  • Each node in a tree has zero or more child nodes.

  • Parent Node:

  • A node that has a child is called the child's parent node.

  • Leaf Nodes:

  • Nodes that do not have any children.

  • Root Node:

  • The topmost node in a tree.

  • Interior Node:

  • Any node which is neither a root, nor a leaf is 
called an interior node.

  • Ancestor Node:

  • Any node higher up than the parent is called an ancestor node.

  • Height:

  • The height of a tree is defined to be the length of the longest path from the root to a leaf in that tree (including the path to root).

  • Depth of node:

  • The length of the path to its root.
  • In the above represented tree:
    • The root node at the top, has no parent.
    • The node labeled 51 has two children labeled 13 and 17 and one parent labeled 91;
    • Node labeled 17, 12, 2 & 4 are leaf nodes.
    • 13, 51 and 42 are interior nodes.

    Binary Tree arrow_upward


  • Every node in a binary tree can have at most two children.
  • The two children of each node are called the left child and right child corresponding to their positions.
  • A node can have only a left child or only a right child or it can have no children at all. (It can have two children as well)
  • Left child is always less than its parent, while right child is greater than its parent.
  • struct tree_node{
    int data;
    struct tree_node *left_child;
    struct tree_node *right_child;
    };
    

    Complete Binary Tree arrow_upward


  • A tree is called complete binary tree if each of its nodes has two children, except the last (leaf) nodes.
  • In other words, every non-terminal node of it must have both children except the leaf nodes.
  • So, at any level the maximum number of nodes is equal to 2(Level no.) . (Maximum number is of nodes at a level is 2^(level no.), i.e. if level is 0 no. of node is 2^0=1 which is our root node. )
  • At level 0, there must be only one node and that is the root node. A at level 1 the maximum nodes must be 2. At level 3 the maximum nodes must be equal to 8.

  • Strictly Binary Tree arrow_upward


  • When every non-leaf node in binary tree is filled with left and right sub-trees, the tree is called strictly binary tree.

  • Extended Binary Tree arrow_upward


  • When every node of a tree has either 0 or 2 children then such a tree is called extended binary tree or 2-tree.

  • Binary Search Tree arrow_upward


  • A Binary Search Tree is a binary tree with the following properties:
    • All items in the left subtree are less than the root.
    • All items in the right subtree are greater or equal to the root.
    • Each subtree is itself a binary search tree.
  • Binary search trees provide an excellent structure for searching a list and at the same time for inserting and deleting data into the list.

  • Basic Property:

  • In a binary search tree,
    • The left subtree contains key values less than the root.  
    • The right subtree contains key values greater than or equal to the root.


    Traversal in Binary Search Tree:

  • Preorder
  • Inorder
  • Postorder
    • These names are chosen according to the sequence in which the root node and its children are visited.
    • Suppose there are only 3 nodes in the tree having the following arrangement:
    •  In–order: n2 n1 n3
    •  Pre-order: n1 n2 n3
    •  Post order: n2 n3 n1


    Preorder Traversal:

  • Algorithm:
  • void preorder(struct tree_node * p){ if(p!=NULL){
    printf(“%d\n”, p->data);
    preorder(p->left_child);
    preorder(p->right_child);
    }
    }
    

    Example:

    Preorder: a b c d f g e

    Note:
  • Preorder traversal is also used to get prefix expression on of an expression tree.

  • Inorder Traversal:

  • Algorithm:
  • void inorder(struct tree_node *p) { if(p!=NULL){
    inorder(p->left_child);
    printf(“%d\n”, p->data);
    inorder(p->right_child);
    } 
    }
    

    Example:

    Inorder: bafdgce

    Note:
  • In case of Binary Search tree, inorder traversal gives nodes in increasing order. 

  • Postorder Traversal:

  • Algorithm:
  • void postorder(struct tree_node *p) { if(p!=NULL){
    postorder(p->left_child);
    postorder(p->right_child);
    printf(“%d\n”, p->data);
    } 
    }
    

    Example:

    Postorder: bfgdeca

    Node:
  • Postorder traversal is also useful to get the postfix expression of an expression tree.

  • Thank You from Kimavi arrow_upward


  • Please email us at Admin@Kimavi.com and help us improve this tutorial.


  • Mark as Complete => Receive a Certificate in Data-Structure


    Kimavi Logo

    Terms and conditions, privacy and cookie policy

    Kimavi @ YouTube | Email Admin @ Kimavi

    Kimavi - A Beautiful Online School


    Learn Python with 500,000 students: Visit TheCodex.Me