Tuesday, January 1, 2013

C++ Code for Some Binary Tree Algorithms

The following C++ code contains several algorithms for binary tree operations.
  • Preorder tree traversal: recursive method; iterative method by using stack data structure; iterative method without stack, but by using a parent node in each tree node.
  • Inorder tree traversal: recursive method; iterative method by using stack data structure; iterative method without stack, but by using a parent node in each tree node.
  • Postorder tree traversal: recursive method; iterative method by using two stacks.
  • Depth first traversal: same as preorder tree traversal
  • Breadth first traversal: print the tree nodes level by level
  • Flattening traversal: flatten the binary tree to a singly linked list for traversal.
  • Encode/Decode a binary tree: Convert a binary tree to a formatted string or convert a formatted string to a binary tree.
  • Check if a binary tree is a binary search tree (BST)
  • Find the largest BST subtree of a binary tree
  • Binary search in a BST
  • Preorder search in a general binary tree
  • Find the lowest common ancestor (LCA) of two binary tree nodes
  • Build a binary tree from inorder and preorder traversal sequence

The tree structure definition is defined here (BinaryTree.h).



#pragma once
#include <string>
using namespace std;

typedef struct TreeNode
{
   TreeNode(int d)
   {
      data = d;
      left = NULL;
      right = NULL;
      parent = NULL;
   }
   int data;
   struct TreeNode *left;
   struct TreeNode *right;
   struct TreeNode *parent;
}
TreeNode;

class BinaryTree
{
public:
   BinaryTree();
   ~BinaryTree();
   void postorderRelease(TreeNode *node);

   void preorder();
   void inorder();
   void postorder();
   void depthFirst();
   void breadthFirst();
   void flatten();
   string encode();
   void decode(const string & s);
   bool isBST();
   TreeNode * binarySearch(int data);
   TreeNode * preorderSearch(TreeNode *node, int data);
   TreeNode * LCA(int data1, int data2);
   void buildFromInPreOrder(const vector<int> &inorder, const vector<int> &preorder);
private:
   void preorder(const TreeNode *node);
   void preorderIterative(const TreeNode *node);
   void preorderIterativeNoStack(const TreeNode *node);
   const TreeNode *preorderNext(const TreeNode *node);
   void inorder(const TreeNode *node);
   void inorderIterative(const TreeNode *node);
   void inorderIterativeNoStack(const TreeNode *node);
   const TreeNode *inorderNext(const TreeNode *node);
   void postorder(const TreeNode *node);
   void postorderIterative(const TreeNode *node);
   void preorderEncode(const TreeNode *node, string *encodeStr, vector<string> *data);
   TreeNode * preorderDecode(const string &encodeStr, const vector<int> &data, string::const_iterator &strItr, vector<int>::const_iterator &dataItr);
   bool isBST(const TreeNode *node, int *min, int *max);
   int BinaryTree::maxBST(TreeNode *node, int *min, int *max, TreeNode *&maxBSTRoot, int *maxBSTTotal);
   TreeNode * BSTLCA(int data1, int data2);
   TreeNode * LCA(TreeNode *rootNode, TreeNode *node1, TreeNode *node2);
   TreeNode * LCAIterative(TreeNode *rootNode, TreeNode *node1, TreeNode *node2);
   TreeNode * buildFromInPreOrder(const vector<int> &inorder, const vector<int> &preorder,
   int inorderStart, int inorderEnd, int preorderStart, int preorderEnd, map<int, int> &inorderMap);
private:
   TreeNode *root;
};
 

The source code is implemented here  (BinaryTree.cpp).



#include <iostream>
#include <sstream>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include "BinaryTree.h"

BinaryTree::BinaryTree()
{
   this->root = NULL;
}

BinaryTree::~BinaryTree()
{
   postorderRelease(root);
}

void BinaryTree::postorderRelease(TreeNode *node)
{
   if (node == NULL)
      return;
   postorderRelease(node->left);
   postorderRelease(node->right);
   delete node;
}

void BinaryTree::preorder()
{
   preorder(root);
   cout<<endl;
   preorderIterative(root);
   cout<<endl;
   preorderIterativeNoStack(root);
   cout<<endl;
}

void BinaryTree::inorder()
{
   inorder(root);
   cout<<endl;
   inorderIterative(root);
   cout<<endl;
   inorderIterativeNoStack(root);
   cout<<endl;
}

void BinaryTree::postorder()
{
   postorder(root);
   cout<<endl;
   postorderIterative(root);
   cout<<endl;
}

void BinaryTree::preorder(const TreeNode  *node)
{
   if (node == NULL)
      return;
   cout<<node->data<<" ";
    preorder(node->left);
    preorder(node->right);
}

void BinaryTree::inorder(const TreeNode  *node)
{
   if (node == NULL)
      return;
    inorder(node->left);
    cout<<node->data<<" ";
    inorder(node->right);
}

void BinaryTree::postorder(const TreeNode  *node)
{
   if (node == NULL)
      return;
    postorder(node->left);
    postorder(node->right);
    cout<<node->data<<" ";
}

void BinaryTree::preorderIterative(const TreeNode *node)
{
   if (node == NULL)
      return;
   stack<const TreeNode *> nodes;
   nodes.push(node);
   while (!nodes.empty())
   {
      const TreeNode *currentNode = nodes.top();
      cout<<currentNode->data<<" ";
      nodes.pop();
      if (currentNode->right)
         nodes.push(currentNode->right);
      if (currentNode->left)
         nodes.push(currentNode->left);
   }
}

//The next node of node X in the preorder sequence is:
// 1. X's left child if it is not NULL;
// 2. X's right child if it is not NULL;
// 3. The right child of the lowest ancester of node X whose left child is also the ancestor of node X and whose right child is not NULL.
// 4. NULL if we finished the search.
const TreeNode * BinaryTree::preorderNext(const TreeNode *node)
{
   if (node == NULL)
      return NULL;
   else if (node->left)
      return node->left;
   else if (node->right)
      return node->right;
   else
   {
      TreeNode *parent = node->parent;
      while (parent != NULL && (node == parent->right || parent->right == NULL))
      {
         node = parent;
         parent = parent->parent;
      }
      if (parent == NULL)
         return NULL;
      else
         return parent->right;
   }
}

//preorder traveral without using a stack. This method depends on the parent pointer
//of the tree node.
void BinaryTree::preorderIterativeNoStack(const TreeNode *node)
{
   while (node)
   {
      cout<<node->data<<" ";
      node = preorderNext(node);
   }
}

void BinaryTree::inorderIterative(const TreeNode *node)
{
   if (node == NULL)
      return;
   stack<const TreeNode *> nodes;
   const TreeNode *currentNode = node;
   while (true)
   {
      if (currentNode)
      {
         nodes.push(currentNode);
         currentNode = currentNode->left;
      }
      else
      {
         if (!nodes.empty())
         {
            currentNode = nodes.top();
            cout<<currentNode->data<<" ";
            nodes.pop();
            currentNode = currentNode->right;
         }
         else
         {
            return;
         }
      }
   }
}

//inorder traveral without using a stack. This method depends on the parent pointer
//of the tree node.
void BinaryTree::inorderIterativeNoStack(const TreeNode *node)
{
   if (node == NULL)
      return;
   while(node->left)
   {
      node = node->left;
   }
   while (node)
   {
      cout<<node->data<<" ";
      node = inorderNext(node);
   }
}

//The next node of node X in the inorder sequence is:
// 1. The left most node of X's right sub tree if X's right child is not NULL;
// 2. the lowest ancester of node X whose left child is also the ancestor of node X.
// 3. NULL if we finished the search.
const TreeNode * BinaryTree::inorderNext(const TreeNode *node)
{
   if (node == NULL)
      return NULL;
   else if (node->right)
   {
      node = node->right;
      while(node->left)
      {
         node = node->left;
      }
      return node;
   }
   else
   {
      TreeNode *parent = node->parent;
      while (parent != NULL && node != parent->left)
      {
         node = parent;
         parent = parent->parent;
      }
      return parent;
   }
}

void BinaryTree::postorderIterative(const TreeNode *node)
{
   if (node == NULL)
      return;
   stack<const TreeNode *> nodes;
   stack<const TreeNode *> outputs;
   nodes.push(node);
   while (!nodes.empty())
   {
      const TreeNode *currentNode = nodes.top();
      outputs.push(currentNode);
      nodes.pop();
      //push left children first
      if (currentNode->left)
         nodes.push(currentNode->left);
      if (currentNode->right)
         nodes.push(currentNode->right);
   }
   while (!outputs.empty())
   {
      cout<<outputs.top()->data<<" ";
      outputs.pop();
   }
}


void BinaryTree::depthFirst()
{
   //preorder is the same as the depthFirst search in graph
   preorder(root);
   cout<<endl;
}

//breadth first traveral, print the nodes level by level
void BinaryTree::breadthFirst()
{
   queue<TreeNode*> queue;
   queue.push(root);
   while (!queue.empty())
   {
      TreeNode *node = queue.front();
      cout<<node->data<<" ";
      queue.pop();
      if (node->left)
         queue.push(node->left);
      if (node->right)
         queue.push(node->right);
   }
   cout<<endl;
}

void BinaryTree::flatten()
{
    TreeNode *tail = root;
    while (tail->left)
   {
        tail=tail->left;
   }
   vector<TreeNode*> tails;
   tails.push_back(tail);
    TreeNode *node = root;
    while(node)
    {
      cout<<node->data<<" ";
        if (node->right)
      {
            tail->left = node->right;
            while(tail->left)
                tail=tail->left;
         tails.push_back(tail);
       }
        node=node->left;
    }
    //restore
    for (unsigned int i = 0; i < tails.size(); i++)
        tails[i]->left = NULL;
   cout<<endl;
}

//encode the binary tree to a string. We use "\n" as delimiter.
string BinaryTree::encode()
{
   vector<string> data;
   string encodeStr = "";
   preorderEncode(root, &encodeStr, &data);
   encodeStr += "\n";
   for (vector<string>::const_iterator itr = data.begin(); itr != data.end(); itr++)
   {
      encodeStr += *itr;
      encodeStr += "\n";
   }
   return encodeStr;
}

//use preorder traversal to encode the binary tree.
//We put extra "dummy" NULL nodes to each tree node so that the tree is a "complete" tree,
//i.e., each tree node has exactly two children (either a "real" tree node or a "dummy" node)
//In the encode string, if it is a tree node, the bit is set to 1,
//if it is a dummy NULL node (e.g. a leaf node has two dummy NULL child nodes), the bit is set to 0.
//Therefore, if the tree has n nodes, then we need 2n+1 bits to encode.
//data vector stores the node data in a preorder sequence.
//we use bit string to encode, i.e. "1110000". It is possible to use int array for a more compact storage.
void BinaryTree::preorderEncode(const TreeNode *node, string *encodeStr, vector<string> *data)
{
   if (data == NULL || encodeStr == NULL)
      throw std::exception();
   if (node == NULL)
   {
      *encodeStr += "0";
      return;
   }
   *encodeStr += "1";
   ostringstream convert; //convert int to string.
   convert<<node->data;
   data->push_back(convert.str());
   preorderEncode(node->left, encodeStr, data);
   preorderEncode(node->right, encodeStr, data);
}

void BinaryTree::decode(const string& s)
{
   vector<int> data;
   string encodeStr = "";
   unsigned int index = 0;
   string currentStr = "";
   while (index < s.length())
   {
      if (s[index]=='\n')
      {
         if (encodeStr.length() > 0)
         {
            int value = atoi(currentStr.c_str());
            data.push_back(value);
         }
         else
         {
            encodeStr = currentStr;
         }
         currentStr = "";
      }
      else
      {
         currentStr += s[index];
      }
      index++;
   }
   string::const_iterator strItr= encodeStr.begin();
   vector<int>::const_iterator dataItr = data.begin();
   root = preorderDecode(encodeStr, data, strItr, dataItr);
}

TreeNode * BinaryTree::preorderDecode(const string &encodeStr, const vector<int> &data, string::const_iterator &strItr, vector<int>::const_iterator &dataItr)
{
   if (strItr == encodeStr.end())
      throw std::exception();
   if (*strItr == '0')
   {
      strItr++;
      return NULL;
   }
   if (dataItr == data.end())
      throw std::exception();
   TreeNode *node = new TreeNode(*dataItr);
   dataItr++;
   strItr++;
   node->left = preorderDecode(encodeStr, data, strItr, dataItr);
   node->right = preorderDecode(encodeStr, data, strItr, dataItr);
   if (node->left)
      node->left->parent = node;
   if (node->right)
      node->right->parent = node;
   return node;
}

//check if a binary tree is a binary search tree (BST).
//for every node of a binary tree, if it satisfies:
//the max of its left sub tree <= node->data <= the min of its right sub tree.
//then it is a BST.
bool BinaryTree::isBST()
{
   int min, max;
   bool r = isBST(root, &min, &max);
   cout<<"min="<<min<<" max="<<max<<endl;

   TreeNode *maxBSTRoot = NULL;
   int maxBSTTotal = 0;
   int total = maxBST(root, &min, &max, maxBSTRoot, &maxBSTTotal);
   cout<<"min="<<min<<" max="<<max<<" total="<<maxBSTTotal<<" max BST root: "<<maxBSTRoot->data<<endl;

   return r;
}

bool BinaryTree::isBST(const TreeNode *node, int *min, int *max)
{
   if (node == NULL || min == NULL || max == NULL)
      return false;
   int leftMin = node->data;
   int leftMax = node->data;
   int rightMin = node->data;
   int rightMax = node->data;
   bool left = true;
   bool right = true;
   if (node->left)
      left = isBST(node->left, &leftMin, &leftMax);
   if (node->right)
      right = isBST(node->right, &rightMin, &rightMax);
   bool self = (leftMax <= node->data) && (node->data <= rightMin);
   *min = leftMin;
   *max = rightMax;
   return left && right && self;
}

//Find the largest subtree which is a BST.
//largest: the tree with largest number of nodes
//subtree: a part of the original tree whose leaf set is a subset of the original tree's leaf set.
int BinaryTree::maxBST(TreeNode *node, int *min, int *max, TreeNode *&maxBSTRoot, int *maxBSTTotal)
{
   if (node == NULL || min == NULL || max == NULL)
      return -1;
   int leftMin = node->data;
   int leftMax = node->data;
   int rightMin = node->data;
   int rightMax = node->data;
   int left = 0;
   int right = 0;
   if (node->left)
      left = maxBST(node->left, &leftMin, &leftMax, maxBSTRoot, maxBSTTotal);
   if (node->right)
      right = maxBST(node->right, &rightMin, &rightMax, maxBSTRoot, maxBSTTotal);
   bool self = (leftMax <= node->data) && (node->data <= rightMin);
   *min = leftMin;
   *max = rightMax;
   if (left >= 0 && right >= 0 && self)
   {
      int total = left + right + 1;
      if (total > *maxBSTTotal)
      {
         *maxBSTTotal = total;
         maxBSTRoot = node;
      }
      return total;
   }
   else
      return -1;
  
}

TreeNode * BinaryTree::binarySearch(int data)
{
   TreeNode *node = root;
   while (node)
   {
      if (node->data == data)
         break;
      else if (node->data > data)
         node = node->left;
      else
         node = node->right;
   }
   return node;
}

TreeNode * BinaryTree::preorderSearch(TreeNode *node, int data)
{
   if (node == NULL)
      return NULL;
   if (node->data == data)
      return node;
    TreeNode *left = preorderSearch(node->left, data);
   if (left)
      return left;
    TreeNode *right = preorderSearch(node->right, data);
   if (right)
      return right;
   return NULL;
}

TreeNode * BinaryTree::LCA(int data1, int data2)
{
   TreeNode* node = BSTLCA(data1, data2);
   cout<<node->data<<" ";
   return node;
}

//find the least common ancester(LCA) of two nodes in BST.
//the input parameters are two numbers.
//we assume the data in each tree node is unique.
TreeNode * BinaryTree::BSTLCA(int data1, int data2)
{
   TreeNode *node = root;
   while (node)
   {
      if (node->data >= data1 && node->data <= data2)
         break;
      else if (node->data > data2)
         node = node->left;
      else
         node = node->right;
   }
   return node;
}

//find the LCA of two nodes in a general binary tree.
//use bottom up approach.
TreeNode * BinaryTree::LCA(TreeNode *rootNode, TreeNode *node1, TreeNode *node2)
{
   if (rootNode == NULL) return NULL;
   if (rootNode == node1 || rootNode == node2)
      return rootNode;
   TreeNode *left = LCA(rootNode->left, node1, node2);
   TreeNode *right = LCA(rootNode->right, node1, node2);
   if (left && right)
      return rootNode;
   else if (left)
      return left;
   else
      return right;
}

//find the LCA of two nodes in a general binary tree.
//we assume the parent link exists in each tree node.
//________
//        \_________
//________/
//
TreeNode * BinaryTree::LCAIterative(TreeNode *rootNode, TreeNode *node1, TreeNode *node2)
{
   if (rootNode == NULL || node1 == NULL || node2 == NULL)
      return NULL;
   int count1 = 0;
   TreeNode *parent1 = node1;
   while (parent1 && parent1 != rootNode)
   {
      count1++;
      parent1 = parent1->parent;
   }
   int count2 = 0;
   TreeNode *parent2 = node2;
   while (parent2 && parent2 != rootNode)
   {
      count2++;
      parent2 = parent2->parent;
   }
   int offset = 0;
   parent1 = node1;
   parent2 = node2;
   if (count1 > count2)
   {
      offset = count1 - count2;
      while (offset > 0)
      {
         offset--;
         parent1 = parent1->parent;
      }
   }
   else
   {
      offset = count2 - count1;
      while (offset > 0)
      {
         offset--;
         parent2 = parent2->parent;
      }
   }
   while(parent1 != parent2 && parent1 && parent2)
   {
      parent1 = parent1->parent;
      parent2 = parent2->parent;
   }
   if (parent1 == NULL || parent2 == NULL)
      return NULL;
   else
      return parent1;
}
void BinaryTree::buildFromInPreOrder(const vector<int> &inorder, const vector<int> &preorder)
{
   map<int, int> inorderMap;
   for (unsigned int i = 0; i < inorder.size(); i++)
   {
      inorderMap[inorder[i]] = i;
   }
  root = buildFromInPreOrder(inorder, preorder, 0, inorder.size() - 1, 0, preorder.size() - 1, inorderMap);
}

TreeNode * BinaryTree::buildFromInPreOrder(const vector<int> &inorder, const vector<int> &preorder,
   int inorderStart, int inorderEnd, int preorderStart, int preorderEnd, map<int, int> &inorderMap)
{
   if (inorderStart > inorderEnd || preorderStart > preorderEnd)
   {
      return NULL;
   }
   int data = preorder[preorderStart];
   TreeNode *node = new TreeNode(data);
   int index = inorderMap[data];
   TreeNode *leftNode = buildFromInPreOrder(inorder, preorder, inorderStart, index - 1,
      preorderStart+1, preorderStart + (index - inorderStart), inorderMap);
   node->left = leftNode;
   if (leftNode)
      leftNode->parent = node;
   TreeNode *rightNode = buildFromInPreOrder(inorder, preorder, index + 1, inorderEnd,
      preorderStart + (index - inorderStart)+ 1, preorderEnd, inorderMap);
   node->right = rightNode;
   if (rightNode)
      rightNode->parent = node;
   return node;
}


 

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)