Binary Tree implemented by Array

How does tree looks when implemented via Array?

  • Left Child - cell[2x]
  • Right Child - cell[2x+1]
  • cell[0] = null

Creation of Binary tree

1
2
3
createBinaryTree()
  create a blank array of 'size'
  update lastUsedIndex to 0

  • Time Complexity : O(1)
  • Space Complextiy : O(n)

Insertion of node

  • Insertion
    • If array is full, return error message
    • Insert at first vacant cell in Array

1
2
3
4
5
6
insertValueInBinaryTree()
  if Tree is full
    return error message
  else
    insert value in first unused cell of array
    update lastUsedIndex

  • Time Complexity : O(1)
  • Space Complextiy : O(1)

Search a node

  • Search
    • When the value to be searched does not exists in the tree
    • When the value to be searched exists in the tree

1
2
3
4
5
searchValueInBinaryTree()
  traverse the entire array from 1 to lastUsedIndex
  if value is found
    return success message
  return error message

  • Time Complexity : O(n)
  • Space Complextiy : O(1)

In-Order Traversal

1
2
3
4
5
6
7
InorderTraversal(index)
  if index > lastUsedIndex
      return
  else
    InorderTraversal(index*2)
    print current index.value
    InorderTraversal(index*2 + 1)

  • Time Complexity : O(n)
  • Space Complextiy : O(n) —- stack에 쌓이기 때문에

Levle-Order Traversal

1
2
3
levelOrderTraversal()
  loop: 1 to lastUsedIndex
    print current index.value

  • Time Complexity : O(n)
  • Space Complextiy : O(1)

Deletion of Node

  • Deletion
    • When the value to be deleted is not existing in the tree
    • When the value to be deleted is exists in the tree
1
2
3
4
5
deleteNodeFromBinaryTree()
  search for desired value in array
    if value found
      replace this cell's value with last cell and update lastUsedIndex
  return error message

  • Time Complexity : O(n)
  • Space Complextiy : O(1)

Delete Binary Tree

1
2
deleteBinaryTree()
  set array as null

  • Time Complexity : O(1)
  • Space Complextiy : O(1)