Tree Data Structure

Properties of Tree

  • Used to represent data in hierarchical form
  • Every Node(ideally) has 2 components(Data & Reference)
  • It has a Root node and 2 disjoint binary tree called left subtree and right subtree



Why we learn Tree?

  • Linked List is better in space efficiency over Array. However, Linked List does not have that good time efficiency on Insertion, Deletion and Searching which is O(n).
  • Tree data structure overcomes the problem of linked list.



Tree Terminologies

  • Root : Node with no parent
  • Edge : Link from parent to child
  • Leaf : Node with no children
  • Sibling : Children of same parent
  • Ancestor : means parent, grand-parent, great grand parent, and so on for a given node
  • Depth of node : Length of the path from root to node
  • Height of node : Length of the path from that node to the deepest node
  • Height of tree : Same as height of Root node
  • Predecessor : Predecessor of a node is the immediate previous node in Inorder traversal of the Binary Tree.
  • Successor : Successor of a node is the immediate next node in Inorder traversal of the Binary Tree.