Delete a Tree

#include<stdio.h>
struct binarysearchtree
{
      int data;
      struct binarysearchtree* left;
      struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;

void tree_free(tree T)
{
  if (T==NULL)
     return;
  else
  {
      tree_free(T->left);
      tree_free(T->right);
      free(T);
  }
}

Count the number of leaves in a tree

#include<stdio.h>
struct binarysearchtree{
        int data;
        struct binarysearchtree* left;
        struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;

int count_leaves(tree T)
{
        if(T==NULL)
            return 0;
        else if(T->left==NULL && T->right==NULL)
            return 1;
        else
            return count_leaves(T->left)+count_leaves(T->right);
}

Check whether there exists a root to leaf path sum equal to a given number

int hasSum(struct node* root, int sum)
{
    if(root == NULL)
        return (sum == 0);

    sum = sum - root->data;

    return hasSum(root->left, sum) || hasSum(root->right, sum);
}

Find if a tree is symmetric / isMirror()

A symmetric binary tree is one where if you draw a vertical line passing through the root node then the left half should be the mirror image of the right half. Here is the recursive code,

int isSymmetric(struct node* l, struct node* r)
{
    if((l == NULL) && (r == NULL))
        return 1;

    if(((l == NULL) && (r != NULL)) ||
            ((l != NULL) && (r == NULL)))
        return 0;

    return isSymmetric(l->left, r->right) && isSymmetric(l->right, r->left);
}

Store the sum of left and right subtrees in a node

int sum(struct node* root)
{
    if(root == NULL)
        return 0;

    int lsum = sum(root->left);
    int rsum = sum(root->right);

    root->data = lsum + rsum + root->data;

    return root->data;
}

Find the kth largest element in a Binary Search Tree

Traverse the tree in descending order and keep a count of number of nodes visited. When this count is equal to 'k', print the element.

void printk(struct node* root, int k)
{
    if(root == NULL)
        return;

    static int index = 0;

    printk(root->right, k);

    if(++index == k)
    {
        printf("%d\n", root->data);
        return;
    }

    printk(root->left, k);
}

Calculate vertical sum of a Binary Tree

Vertical sums of a binary tree are the sum of its each vertical column. For e.g. consider the below tree,

                 5
             /        \
          3            8
         /  \          /    \
       2     4      6     9


Vertical Sum for first column: 2
Vertical Sum for second column: 3
Vertical Sum for third column: 15 (5+4+6)
Vertical Sum for fourth column: 8
Vertical Sum for fifth column: 9

Output: 2 3 15 8 9

Algorithm:
- start from root and hash its value in a map using a key, say, 'key_col'
- recursively hash left and right children with key value 'key_col-1' and 'key_col+1'
- if the key entry is not present in the hash map then create one and set value as 'root->data'
- if the key entry is already present then just add 'root->data' to the existing value

In the end, we have vertical sum stored in the hash map. Here is the code,

void mapNode(struct node* root, map& m, int col)
{
    if(root == NULL)
        return;
 
    map::iterator it = m.find(col);

    //if column is already mapped and map already
    //has some value stored for the column then
    //add root->data to already stored value, otherwise,
    //just store root->data.
    if(it == m.end())
        m.insert(pair(col, root->data));
    else
        it->second += root->data;

    mapNode(root->left, m, col-1);
    mapNode(root->right, m, col+1);
}

int main()
{
    struct node *root=NULL;
    map m;
    map::iterator iter;

    insert(&root, 50);
    insert(&root, 25);
    insert(&root, 100);
    insert(&root, 30);
    insert(&root, 20);
    insert(&root, 75);

    mapNode(root, m, 0);

    for(iter = m.begin(); iter != m.end(); iter++)
        printf("%d ", iter->second);

    printf("\n");

    return 0;
}

Print ancestors of a node in a Binary Tree

int isAncestor(struct node* root, int n)
{
    if(root == NULL)
        return 0;

    if(root->data == n)
        return 1;

    if(isAncestor(root->left, n) || isAncestor(root->right, n))
    {
        printf("%d\n", root->data);
        return 1;
    }

    return 0;
}

Serialization/Deserialization of a Binary Tree

Serialize:
to Array - (for node 'i', store left child at '2i+1' & right child at '2i+2')

Assume we have a binary tree below:

    _30_
   /        \
 10      20
 /          /  \
50     45  35

Using pre-order traversal, the algorithm should write the following to a file:

30 10 50 # # # 20 45 # # 35 # #

void writeBinaryTree(BinaryTree *p, ostream &out)
{
    if (!p)
    {
        out << "# ";
    }
    else
    {
        out << p->data << " ";
        writeBinaryTree(p->left, out);
        writeBinaryTree(p->right, out);
    }
}


Deserialize:


Reading the binary tree from the file is similar. We read tokens one at a time using pre-order traversal. If the token is a sentinel, we ignore it. If the token is a number, we insert it to the current node, and traverse to its left child, then its right child.

void readBinaryTree(BinaryTree *&p, ifstream &fin)
{
    int token;
    bool isNumber;
    if (!readNextToken(token, fin, isNumber))
        return;
    if (isNumber)
    {
        p = new BinaryTree(token);
        readBinaryTree(p->left, fin);
        readBinaryTree(p->right, fin);
    }
}

Construct a Binary Tree, given its Inorder and preorder

Consider the following tree,

               5
           /        \
         2          7
      /   \         /
     1    4      6

Inorder: 1 2 4 5 6 7
Preorder: 5 2 1 4 7 6

Algorithm:
1. Take first element from Preorder (in this case 5) and find it in Inorder.
2. Elements on the left side of '5' (1 2 4) form the left subtree of '5' and similarly elements on the right side (6 7) form right sub tree.
3. Recursively select each element from Preorder and create its left and right subtrees from Inorder.

struct node* create(int* in, int* pre, int inStrt, int inEnd)
{
    if(inStrt > inEnd)
        return NULL;

    int i;
    static int preIndex = 0;

    //create node from preOrder
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = pre[preIndex];

    //find node in inOrder
    for(i=inStrt; i<=inEnd; i++)
        if(in[i] == pre[preIndex])
            break;

    preIndex++;
   
    //recursively call create for the left and right
    //half of inOrder created by preOrder
    temp->left = create(in, pre, inStrt, i-1);
    temp->right = create(in, pre, i+1, inEnd);

    return temp;
}

Diameter of a Binary Tree

            5

         /      \
       2         9
     /    \      /
    1    4    7

Diameter: 5 (1-2-5-9-7 or 4-2-5-9-7)

int height(struct node* root)
{
    if(root == NULL)
        return 0;

    int lh = height(root->left);
    int rh = height(root->right);

    return 1 + MAX(lh, rh);
}

int diameter(struct node* root)
{
    if(root == NULL)
        return 0;

    int lheight = height(root->left);
    int rheight = height(root->right);

    int ldia = diameter(root->left);
    int rdia = diameter(root->right);

    return MAX(1 + lheight + rheight, MAX(ldia, rdia));
}

Print Edge Nodes (Boundary) of a Binary Tree

    _30_

   /    \
  10    20
 /     /  \
50    45  35

The correct solution should print 30, 10, 50, 45, 35, 20.

        ______30______
       /              \
    __20__          __40__
   /      \        /      \
  10      25      35      50
 /  \       \            /
 5  15      28          41

The correct solution should print 30, 20, 10, 5, 15, 28, 35, 41, 50, 40.

   _______________28_______________
  /                                \
  4____                        ____69
       \                      /
      __8__                __56__
     /     \              /      \
   __7     12__        __34    __27__
  /            \      /       /      \
  5_          _13    _2      _3      39
    \        /      /       /
     6      11     10       9

correct output of: 28, 4, 8, 7, 5, 6, 11, 10, 9, 39, 27, 56, 69.

Hint:
To solve this problem, you first need to pay attention to these three key areas:

• Printing the leftmost edges from top to bottom. When a node is a leftmost edge, its left child must also be a leftmost edge.
• Printing the leaves from left to right. Remember depth-first traversal?
• Printing the rightmost edges. You would need to print from bottom to top. The key is printing in the opposite order. Easy if you know how to manipulate recursion into a stack-based solution. Remember post-order traversal?

Solution:
We could divide the tree into two subtrees. One is the left subtree, and the other is the right subtree.

For the left subtree, we print the leftmost edges from top to bottom. Then we print its leaves from left to right.

For the right subtree, we print its leaves from left to right, then its rightmost edges from bottom to top.

Printing the leaves from left to right order is a classic example of depth-first traversal. How do you know if a node is a leaf? Easy, if the node does not have both left and right children.

Printing the leftmost edges is just a trivial addition to the depth-first traversal. When a node is a leftmost edge, then its left child must also be a leftmost edge. We could use a variable to pass this information down the tree. Please note that you must add the condition to avoid printing the node twice (a node could be a leftmost edge as well as a leaf node).

Printing the rightmost edges from bottom to top is easy if you realize the trick of manipulating recursion as a stack. Try relate this with how post-order traversal works. When calling recursive functions, function calls are pushed onto a stack, and therefore you could use the implicit stack to your advantage. This trick is especially handy when applied in situation where you need to reverse the order of operations.

#include<stdio.h>
#include<stdlib.h>

struct node {
    struct node *left;
    struct node *right;
    int data;
};

struct node *newnode(int data)
{
        struct node *node=(struct node *)malloc(sizeof(struct node));
        node->data=data;
        node->left=NULL;
        node->right=NULL;
        return node;
}

void printLeftBoundary(node *root) {

    if(root==NULL) return;
    if(root->left) {
       printf("%d ",root->data);
       printLeftBoundary(root->left);
    }
    else if(root->right) {
       printf("%d ",root->data);
       printLeftBoundary(root->right);
    }
}

void printLeafBoundary(node *root) {

    if(root) {
   
       printLeafBoundary(root->left);
      
       if(root->left==NULL && root->right==NULL)
          printf("%d ",root->data);
         
       printLeafBoundary(root->right);
    }
}

void printRightBoundary(node *root)
{
    if(root==NULL) return;
    if(root->right) {
       printRightBoundary(root->right);
       printf("%d ",root->data);
    }
    else if(root->left) {
       printRightBoundary(root->left);
       printf("%d ",root->data);
    }
}

void printBoundary(node *root)
{
if(root)
    {
        printf("%d ", root->data);
       
        printLeftBoundary(root->left);
       
        printLeafBoundary(root);
       
        printRightBoundary(root->right);
    }
}

int main()
{
    struct node *root=newnode(1000);
    root->left=newnode(500);
    root->right=newnode(1500);
    root->left->right=newnode(510);
    root->left->right->right=newnode(600);   
    root->left->left=newnode(240);
    root->left->left->left=newnode(120);
    root->left->left->right=newnode(300);   
    root->right->left=newnode(1300);
    root->right->left->right=newnode(1320);   
   
    printBoundary(root);
   

    return 0;
}

Time Complexity
PrintLeftBoundary - O(h), where h is height of tree, log(n) nodes on left are visited once
PrintLeafBoundary - O(n), as each node is visited once
PrintRightBoundary - O(h), where h is height of tree, log(n) nodes on right are visited once.

O(n+2h) total time complexity 

Lowest Common Ancestor of a Binary Search Tree (BST)

        _______6______

       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

Using the above tree as an example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. LCA of nodes 2 and 4 is 2

Hint:

A top-down walk from the root of the tree is enough.

Solution:

There’s only three cases you need to consider.

1. Both nodes are to the left of the tree.
2. Both nodes are to the right of the tree.
3. One node is on the left while the other is on the right.

For case 1), the LCA must be in its left subtree. Similar with case 2), LCA must be in its right subtree. For case 3), the current node must be the LCA.

Therefore, using a top-down approach, we traverse to the left/right subtree depends on the case of 1) or 2), until we reach case 3), which we concludes that we have found the LCA.

A careful reader might notice that we forgot to handle one extra case. What if the node itself is equal to one of the two nodes? This is the exact case from our earlier example! (The LCA of 2 and 4 should be 2). Therefore, we add another case number ):

4. When the current node equals to either of the two nodes, this node must be the LCA too.

The run time complexity is O(h), where h is the height of the BST. Translating this idea to code is straightforward (Note that we handle case 3) and 4) in the else statement to save us some extra typing

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root || !p || !q) return NULL;
  if (max(p->data, q->data) < root->data)
    return LCA(root->left, p, q);
  else if (min(p->data, q->data) > root->data)
    return LCA(root->right, p, q);
  else
    return root;
}

Lowest Common Ancestor of a Binary Tree "WITHOUT" Parent pointers

        _______3______

       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

Using the tree above as an example, the LCA of nodes 5 and 1 is 3. Please note that LCA for nodes 5 and 4 is 5.

Hint:

Top-down or bottom-up? Consider both approaches and see which one is more efficient.

A Top-Down Approach (Worst case O(n²) ):

Let’s try the top-down approach where we traverse the nodes from the top to the bottom. First, if the current node is one of the two nodes, it must be the LCA of the two nodes. If not, we count the number of nodes that matches either p or q in the left subtree (which we call totalMatches). If totalMatches equals 1, then we know the right subtree will contain the other node. Therefore, the current node must be the LCA. If totalMatches equals 2, we know that both nodes are contained in the left subtree, so we traverse to its left child. Similar with the case where totalMatches equals 0 where we traverse to its right child.

// Return #nodes that matches P or Q in the subtree.
int countMatchesPQ(Node *root, Node *p, Node *q) {
  if (!root) return 0;
  int matches = countMatchesPQ(root->left, p, q) + countMatchesPQ(root->right, p, q);
  if (root == p || root == q)
    return 1 + matches;
  else
    return matches;
}

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root || !p || !q) return NULL;
  if (root == p || root == q) return root;
  int totalMatches = countMatchesPQ(root->left, p, q);
  if (totalMatches == 1)
    return root;
  else if (totalMatches == 2)
    return LCA(root->left, p, q);
  else /* totalMatches == 0 */
    return LCA(root->right, p, q);
}

What is the run time complexity of this top-down approach?

First, just for fun, we assume that the tree contains n nodes and is balanced (with its height equals to log(n) ). In this case, the run time complexity would be O(n). Most people would guess a higher ordered complexity than O(n) due to the function countMatchesPQ() traverses the same nodes over and over again. Notice that the tree is balanced, you cut off half of the nodes you need to traverse in each recursive call of LCA() function. The proof that the complexity is indeed O(n) is left as an exercise to the reader.

What if the tree is not necessarily balanced? Then in the worst case the complexity could go up to O(n²). Why? Could you come up with such case? (Hint: The tree might be a degenerate tree).

A Bottom-up Approach (Worst case O(n) ):Using a bottom-up approach, we can improve over the top-down approach by avoiding traversing the same nodes over and over again.

We traverse from the bottom, and once we reach a node which matches one of the two nodes, we pass it up to its parent. The parent would then test its left and right subtree if each contain one of the two nodes. If yes, then the parent must be the LCA and we pass its parent up to the root. If not, we pass the lower node which contains either one of the two nodes (if the left or right subtree contains either p or q), or NULL (if both the left and right subtree does not contain either p or q) up.

Sounds complicated? Surprisingly the code appears to be much simpler than the top-down one.

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

Maximum Height (Depth) of a Binary Tree

The maximum height of a binary tree is defined as the number of nodes along the path from the root node to the deepest leaf node. Note that the maximum height of an empty tree is 0.

Recursive Solution:
We can solve this easily using recursion. Why? Because each of the leftChild and rightChild of a node is a sub-tree itself. We first compute the max height of left sub-tree, then compute the max height of right sub-tree. Therefore, the max height of the current node is the greater of the two max heights + 1. For the base case, the current node is NULL, we return zero. NULL signifies there is no tree, therefore its max height is zero.

int maxHeight(BinaryTree *p)
{
     if (!p) return 0;

     int left_height = maxHeight(p->left);
     int right_height = maxHeight(p->right);

     return (left_height > right_height) ? left_height + 1 : right_height + 1;
}

Insert in a BST

Insert()

Insert() -- given a binary search tree and a number, insert a new node with the given number into the tree in the correct place. The insert() code is similar to lookup(), but with the complication that it modifies the tree structure. As described above, insert() returns the new tree pointer to use to its caller. Calling insert() with the number 5 on this tree...
2
/ \
1 10

returns the tree...

2
/ \
1 10
/
5

The solution shown here introduces a newNode() helper function that builds a single node. The base-case/recursion structure is similar to the structure in lookup() -- each call checks for the NULL case, looks at the node at hand, and then recurs down the left or right subtree if needed.

/*
 Helper function that allocates a new node
 with the given data and NULL left and right
 pointers.
*/
struct node* NewNode(int data) {
  struct node* node = new(struct node);    // "new" is like "malloc"
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
} 

/*
 Give a binary search tree and a number, inserts a new node
 with the given number in the correct place in the tree.
 Returns the new root pointer which the caller should
 then use (the standard trick to avoid using reference
 parameters).
*/
struct node* insert(struct node* node, int data) {
  // 1. If the tree is empty, return a new, single node
  if (node == NULL) {
    return(newNode(data));
  }
  else {
    // 2. Otherwise, recur down the tree
    if (data <= node->data) node->left = insert(node->left, data);
    else node->right = insert(node->right, data);

    return(node); // return the (unchanged) node pointer
  }
}

Check whether two trees are structurally identical

/*
 Given two trees, return true if they are
 structurally identical.
*/
int sameTree(struct node* a, struct node* b) {
  // 1. both empty -> true
  if (a==NULL && b==NULL) return(true);
  // 2. both non-empty -> compare them
  else if (a!=NULL && b!=NULL) {
    return(
      a->data == b->data &&
      sameTree(a->left, b->left) &&
      sameTree(a->right, b->right)
    );
  }
  // 3. one empty, one not -> false
  else return(false);
}

Check whether a given tree is a BST

/*
 Returns true if a binary tree is a binary search tree.
*/
int isBST(struct node* node) {
  if (node==NULL) return(true);
  // false if the max of the left is > than us

  // (bug -- an earlier version had min/max backwards here)
  if (node->left!=NULL && maxValue(node->left) > node->data)
    return(false);

  // false if the min of the right is <= than us
  if (node->right!=NULL && minValue(node->right) <= node->data)
    return(false);

  // false if, recursively, the left or right is not a BST
  if (!isBST(node->left) || !isBST(node->right))
    return(false);

  // passing all that, it's a BST
  return(true);
} 

OR

/*
 Returns true if the given tree is a binary search tree
 (efficient version).
*/
int isBST2(struct node* node) {
  return(isBSTUtil(node, INT_MIN, INT_MAX));
}
/*
 Returns true if the given tree is a BST and its
 values are >= min and <= max.
*/
int isBSTUtil(struct node* node, int min, int max) {
  if (node==NULL) return(true);

  // false if this node violates the min/max constraint
  if (node->data<min || node->data>max) return(false);

  // otherwise check the subtrees recursively,
  // tightening the min or max constraint
  return
    isBSTUtil(node->left, min, node->data) &&
    isBSTUtil(node->right, node->data+1, max)
  );
}

Create a new duplicate node for each node in a BST

/*

 For each node in a binary search tree,
 create a new duplicate node, and insert
 the duplicate as the left child of the original node.
 The resulting tree should still be a binary search tree.
 So the tree...
    2
   / \
  1   3

 Is changed to...
       2
      / \
     2   3
    /   /
   1   3
  /
 1

*/

void doubleTree(struct node* node) {
  struct node* oldLeft;

  if (node==NULL) return;

  // do the subtrees
  doubleTree(node->left);
  doubleTree(node->right);

  // duplicate this node to its left
  oldLeft = node->left;
  node->left = newNode(node->data);
  node->left->left = oldLeft;
}

Mirror a BST

/*

 Change a tree so that the roles of the
 left and right pointers are swapped at every node.
 So the tree...
       4
      / \
     2   5
    / \
   1   3

 is changed to...
       4
      / \
     5   2
        / \
       3   1
*/

void mirror(struct node* node) {
  if (node==NULL) {
    return;
  }
  else {
    struct node* temp;

    // do the subtrees
    mirror(node->left);
    mirror(node->right);

    // swap the pointers in this node
    temp = node->left;
    node->left = node->right;
    node->right = temp;
  }
}