Binary Tree Operations

Finding the number of nodes in a binary tree

Any of the four traversal methods can be used, since each method visits each node exactly one time.

while (there are elements in the tree)
   cnt++

   if (there is a left child)
      push onto a queue
   endif
   if (there is a right child)
      push onto a queue
   endif

   pop the queue
endwhile

Finding the height of a binary tree

The height of a binary tree can be found by performing a postorder traversal. The height of the left subtree is determined; then the height of the right subtree is determined. During the "visit" step, the height of the tree is determined as:

height = maximum{leftHeight, rightHeight} + 1

if(ptr is null)
  return 0
endif

leftHeight = height(ptr->leftChild)
rightHeight = height(ptr->rightChild)

if (leftHeight > rightHeight)
  return leftHeight + 1
else
  return rightHeight + 1
endif

Finding the number of leaves in a binary tree

Any of the four traversal methods can be used, since each method visits each node exactly one time.

while (there are elements in the tree)
   if (leftChild is null AND rightChild is null)
     leaveCnt++

   if (there is a left child)
      push onto a queue
   endif
   if (there is a right child)
      push onto a queue
   endif

   pop the queue
endwhile

Finding the width of a binary tree

The width of a binary tree is the maximum number of elements on one level of the tree.

isRowEmpty -- indicates if there is an empty row below the current level
q1, q2     -- queues to hold the address of nodes in the tree
ptr        -- pointer to a binary tree node
width      -- width of 1 level
maxWidth   -- the maximum width

initialize isRowEmpty to false
initialize width and maxWidth to 0

push the address of the first node onto q1

while (isRowEmpty == false)
   set isRowEmpty to true
   
   while(q1 is not empty)
     ptr = pop q1

     if (ptr is not null)
       increment width
       push address of ptr's leftChild on q2
       push address of ptr's rightChild on q2

       if (ptr's leftChild is not null OR ptr's rightChild is not null)
         isRowEmpty = false
       endif
     endif
   endwhile
   
   while (q2 is not empty)
     move items from q2 to q1
   endwhile
   
   if (width > maxWidth)
     maxWidth = width
   endif
   
   set width to 0
endwhile

Deleting a binary tree

The delete a binary tree, all of its nodes need to be deleted. This can be done by performing a postorder traversal. During the "visit" step, the node is deleted. By doing this, the left subtree will be deleted, then the right subtree, and finally the root.

delete ()
  delete(root)
  set root to null


delete(pointer to a tree node)
  if (pointer is not null)
    delete(pointer leftChild)
    delete(pointer rightChild)
    delete pointer
  endif