Binary Tree

Binary Tree Node

public class BTNode
{
   char element;
   BTNode left;
   BTNode right;

   public BTNode(){}

   public BTNode(char element)
   {
      this.element = element;
   }

   public Node (int element, BTNode left, BTNode right)
   {
      this.element = element;
      this.left = left;
      this.right = right;
   }
}

Binary tree traversals.

The next link has a useful tool to visualize preorder,
inorder, postorder, and level order binary tree traversals:

http://nova.umuc.edu/~jarc/idsv/lesson1.html



Preorder traversal: print node element, then visit left and right nodes recursively.


public void preorder(BTNode node)
{
   if (node != null)
   {
      System.out.print(node.element + " ");
      preorder(node.left);
      preorder(node.right);
   }
}

Postorder traversal: visit left and right nodes, then print node element.


public void postorder(BTNode node)
{
   if (node != null)
   {
      postorder(node.left);
      postorder(node.right);
      showNode(node);
   }
}

Inorder traversal: visit left, print node element, visit right.


public void inorder(BTNode node)
{
   BTNode child;
   if(node != null)
   {
      inorder(node.left);
      showNode(node);
      inorder(node.right);
   }
}


Other Binary Tree routines.

isEven returns true if the binary tree has an even number of nodes, otherwise returns false. If the tree is null returns true.


public boolean isEven(BTNode node)
{
   if(node == null)
      return true;
   else if(node.left == null && node.right == null)
      return false;
   else
   return (isEven(node.left) != isEven(node.right));
}



noLeftChildren returns true if the Binary tree has no left children, otherwise returns false.

//Iterative version:

public boolean noLeftChildren(BTNode node)
{
   while(node != null)
   {
      if (node.left != null)
         return false;
      node = node.right;
   }
   return true;

}

//Recursive version

public boolean noLeftChildren(BTNode node)
{
   if (node == null)
      return true;
   else if(node.left != null)
      return false;
   else
   return (noLeftChildren(node.right));
}

fullNodesCount returns the number of full nodes in a binary tree.

public int fullNodesCount( BTNode node)
{
   int counter = 0;
   if (node == null)
      return 0;
   else if (node.left != null && node.right != null)
      counter ++;
   counter += fullNodesCount(node.left);
   counter += fullNodesCount(node.right);
   return counter;
}

A) Given a binary tree of integer elements, write a function which performs a PREORDER traversal. When the function "visits" a node, print out the element.

public void preorder(BTNode node)
{
   if (node != null)
   {
      System.out.print(node.element + " ");
      preorder(node.left);
      preorder(node.right);
   }
}

B) Repeat, but print out the elements only at every other layer, starting from the root. You decide on the appropriate parameters to your function. Also show the initial call to your function.


As an example, this tree:



would result in the following output: 5, 2, 6, 8, 1, 7.


// print must be set to true for the initial call
// to everyOtherPreorder

public void everyOtherPreorder(Node node, boolean print)
{
   if (node != null)
   {
      if(print)
         showNode(node);
      everyOtherPreorder(node.left, !print);
      everyOtherPreorder(node.right, !print);
   }
}

Given a binary tree of integer elements, return a copy of the same tree. Consider what the return value should be if the given tree happens to be NULL.

public Node copyTree(Node T)
{
   if(T == null)
      return null;
   Node left = copyTree(T.left);
   Node right = copyTree(T.right);
   return (new Node(T.element, left, right));
}

Consider these two binary trees, where the first tree consists of identical integer elements:



The problem is: Given a binary tree (but NOT a key x), return TRUE (1) if every node in the tree contains exactly the same element. It does not matter what the value is, just that all values are the same. Otherwise, return FALSE (0). If the tree is empty, return TRUE.

In the example, the function would return TRUE for the first tree, but FALSE for the second tree.

Do not call any other functions, and do not do any type of "counting''.

public class BTree
{
   BTNode root;

   public BTree(){}
   public BTree(int element)
   {
      root = new BTNode(element);
   }

   public boolean allSame(BTNode node)
   {
      if (node != null)
      {
         if (node.element != root.element)
            return false;
         else
            return(allSame(node.left) && allSame(node.right));
         }
   return true;
   }

   //Testing
   public static void main(String args[])
   {
      BTree T = new BTree(5);
      T.root.left = new BTNode(4);
      T.root.right = new BTNode(9);
      T.root.left.left = new BTNode(2);
      T.root.left.right = new BTNode(8);
      T.root.left.left.left = new BTNode(10);
      T.root.left.left.left.left = new BTNode(15);
      T.root.left.left.left.left.left = new BTNode(20);
      T.root.left.left.left.right = new BTNode(6);
      T.root.right.left = new BTNode(1);
      T.root.right.left.right = new BTNode(3);
      T.root.right.left.right.left = new BTNode(7);

      System.out.println("Allsame?: " + T.allSame(T.root));

      BTree T2 = new BTree(5);
      T2.root.left = new BTNode(5);
      T2.root.right = new BTNode(5);
      T2.root.left.left = new BTNode(5);
      T2.root.left.right = new BTNode(5);
      T2.root.left.left.left = new BTNode(5);
      T2.root.left.left.left.left = new BTNode(5);
      T2.root.left.left.left.left.left = new BTNode(5);
      T2.root.left.left.left.right = new BTNode(5);
      T2.root.right.left = new BTNode(5);
      T2.root.right.left.right = new BTNode(5);
      T2.root.right.left.right.left = new BTNode(5);

      System.out.println("Allsame?: " + T2.allSame(T2.root));
   }
}

Write a function which is provided a pointer to the root of a (possibly empty) binary tree, and performs this operation: swap the character element of the given node with the element of the node of the left child. The entire tree should undergo this transformation, starting from the root. Do not move any pointers, just move elements. If the node does not have a left child, then a swap does not occur. Obviously, if the tree is empty, there is nothing to do. Note that the function does not have a return type.
Example of "swap with left":




public void swapWithLeft(BTNode node)
{
   char temp;
   if (node != null)
   {
      if(node.left != null)
      {
         temp = node.element;
         node.element = node.left.element;
         node.left.element = temp;
      }
      swapWithLeft(node.left);
      swapWithLeft(node.right);
   }
}