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;
}
is added in the main toolbar.
