Traverse Binary Tree

Traversing all nodes of Binary Tree(Linked List implementation)

Depth first search

  1. PreOrder Traversal
  2. InOrder Traversal
  3. PostOrder Traversal

Breadth first search

  1. LevelOrder Traversal

* PreOrder Traversal(Using Stack)

  • Root
  • Left Subtree
  • Right Subtree
1
2
3
4
5
6
7
8
9
preorderTraverse(root){  ----------------T(n)
  if(root equals null){
    return error message
  } else {
    print root
    preorderTraversal(root.left)  -------T(n/2)
    preorderTraversal(root.right) -------T(n/2)
  }
}

  • Time Complexity - O(n)
  • Space Complexity - O(n) : Recursive call로 많은 노드가 스택에 push, pull 되기 때문에

* In-Order Traversal(Using Stack)

  • Left Subtree
  • Root
  • Right Subtree
1
2
3
4
5
6
7
8
9
inorderTraverse(root){  ----------------T(n)
  if(root equals null){
    return error message
  } else {
    inorderTraversal(root.left)  -------T(n/2)
    print root
    inorderTraversal(root.right) -------T(n/2)
  }
}

  • Time Complexity - O(n)
  • Space Complexity - O(n)

* Post-Order Traversal(Using Stack)

  • Left Subtree
  • Right Subtree
  • Root
1
2
3
4
5
6
7
8
9
postorderTraverse(root){  ----------------T(n)
  if(root equals null){
    return error message
  } else {
    postorderTraversal(root.left)  -------T(n/2)
    postorderTraversal(root.right) -------T(n/2)
    print root
  }
}

  • Time Complexity - O(n)
  • Space Complexity - O(n)

* Level-Order Traversal(Using Queue)

1
2
3
4
5
6
7
8
levelOrderTraversal(root){
  create a Queue(Q)
  enqueue(root)
  while(Queue is not empty){
    enqueue() the child of the first element
    dequeue() and print
  }
}

* Time Complexity - O(n) * Space Complexity - O(n)



* Searching a node(Using Level-order Traversal)

1
2
3
4
5
6
7
8
9
10
searchForGivenValue(value){
  if(root == null){
    return error message
  } else {
    do a level order traversal
      if value found
        return success message
    return unsuccessful message
  }
}

* Time Complexity - O(n) * Space Complexity - O(n)

* Insertion of node(Using Level-order Traversal)

  • Insertion
    • When the root is blank
    • Insert at first vacant child

1
2
3
4
5
6
7
8
insertNodeInBinaryTree(){
  if(root is blank){
    insert new node at root
  } else {
    do a level order traversal and find the first blank space
    insert in that blank place
  }
}

* Time Complexity - O(n) * Space Complexity - O(n)

* Deletion of node(Using Level-order Traversal)

  • Insertion
    • When the value to be deleted is not existing in the tree
    • When the value to be deleted exists in the tree

1
2
3
4
5
deleteNodeFromBinaryTree()
  search for the node to be deleted
  find deepest node in the tree(using level order traversal)
  copy deepest node's data in current node
  delete deepest node

* Time Complexity - O(n) * Space Complexity - O(n)