Monthly Archives: March 2014

Vertical Order traversal of a tree from the bottom

by 
#include <iostream>
#include <vector>
#include <memory>
#include <map>

using namespace std;

typedef map<int, vector<int>> Map;

class Tree {
  
  class TreeNode {
    public:
      
      unique_ptr<TreeNode> left, right;
      int el;

      explicit TreeNode(int _el) : el{_el} {}

      TreeNode() = default;
      ~TreeNode() = default;

      TreeNode(TreeNode &&) = default;
      TreeNode& operator=(TreeNode &&) = default;

      TreeNode(TreeNode const& ) = delete;
      TreeNode& operator=(TreeNode const&) = delete;

      /*
        Populates Map in vertical order
      */

      void verticalOrder(Map &m,  int distance) const {
        m[distance].push_back(el);  

        if (left != nullptr) {
          left->verticalOrder(m, distance - 1);
        }

        if (right != nullptr) {
          right->verticalOrder(m, distance + 1);
        }
      }
  };


  unique_ptr<TreeNode> root;

  /*
    Example Tree:

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

  */

  public:

    Tree() {
      root = unique_ptr<TreeNode>{new TreeNode{1}};
      root->left = unique_ptr<TreeNode>{new TreeNode{2}};
      root->right = unique_ptr<TreeNode>{new TreeNode{3}};
      root->left->left = unique_ptr<TreeNode>{new TreeNode{4}};
      root->left->right = unique_ptr<TreeNode>{new TreeNode{5}};
      root->right->left = unique_ptr<TreeNode>{new TreeNode{6}};
      root->right->right = unique_ptr<TreeNode>{new TreeNode{7}};
      root->right->left->right = unique_ptr<TreeNode>{new TreeNode{8}};
      root->right->right->right = unique_ptr<TreeNode>{new TreeNode{9}};
    }

    Map verticalOrder() {

      Map m;

      if (root != nullptr) {
        root->verticalOrder(m, 0);
      }

      return m;
    }
};


int main(int argc, char const *argv[]) {
  Tree t;
  Map m {t.verticalOrder()};

  for (auto& p : m) {
    for (auto el : p.second) {
      cout << el << " ";  
    }  
    cout << endl;
  }

  return 0;
}

Given a binary tree, defining a term “complete path sum” as sum of values of nodes lying in a path from root to the leaf; Now given a value ‘k’, prune the nodes for whose complete path sum is smaller than k

by 
#include <stdio.h>

struct TreeNode
{
  TreeNode *left, *right;
  int el;

  explicit TreeNode(int _el) : left(NULL), right(NULL), el(_el) {}

  ~TreeNode() {
    delete left;
    delete right;
    
    left = NULL;
    right = NULL;  
  }

  private:
    TreeNode(const TreeNode&);
    TreeNode operator=(const TreeNode&);
};

typedef TreeNode* Tree;

bool pruneTree(Tree t, int k, int sum) 
{
  if (t == NULL) return sum < k;
  
  sum += t->el;

  bool l = pruneTree(t->left, k, sum);
  bool r = pruneTree(t->right, k, sum);

  if (l) {
    delete(t->left);  
    t->left = NULL;
  } 

  if (r) {
    delete(t->right);  
    t->right = NULL;
  } 

  return l && r;
} 

Tree pruneTree(Tree t, int k) 
{
  if (pruneTree(t, k, 0)) {
    delete t;
    return NULL;  
  }  

  return t;
}

void preorder(Tree t)
{
  if (t == NULL) return;
  printf("%d ", t->el);
  preorder(t->left);  
  preorder(t->right);  
}

/*
  Example Tree:

          1
       /    \
      2      3
     / \    /  \
    4   5  6    7
   /     \     / 
  8       9   10

*/

Tree newTree() 
{
  TreeNode *root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);
  root->left->left = new TreeNode(4);
  root->left->right = new TreeNode(5);
  root->right->left = new TreeNode(6);
  root->right->right = new TreeNode(7);
  root->left->left->left = new TreeNode(8);
  root->left->right->right = new TreeNode(9);
  root->right->right->left = new TreeNode(10);

  return root;
}

int main(int argc, char const *argv[])
{
  Tree t  = newTree();
  preorder(pruneTree(t, 17));
  printf("\n");
  return 0;
}

Given the root of the binary tree and a pointer to any random node in that tree, the objective is to print all the nodes at ‘k’ distance from the given random node

by 
#include <stdio.h>

struct TreeNode
{
  TreeNode *left, *right;
  int el;

  explicit TreeNode(int _el) : left(NULL), right(NULL), el(_el) {}
};

typedef TreeNode* Tree;

/*
  prints all the descendent nodes which are k distance from t
*/

void printNodes(Tree t, int k) 
{
  if (t == NULL || k < 0) {
     return;
  };

  if (k == 0)  {
    printf ("%d", t->el);  
  }
  else {
    printNodes(t->left, k - 1);
    printNodes(t->right, k - 1);
  }
}

/*
  prints all the nodes which are k distance from the given node n
  returns the distance of t from n
*/

int printNodes(Tree t, TreeNode *n,  int k) 
{
  if (t == NULL) return -1;

  if (t == n) {
    printNodes(t, k);  
    return 0;
  }

  int d;

  if (t->left) {
    d = printNodes(t->left, n, k);

    if (d >= 0) {
      d++;

      if (d == k) {
        printf("%d", t->el);  
      }
      else {
        printNodes(t->right, k - d - 1);  
      }
      return d;
    }
  }

  if (t->right) {
    d = printNodes(t->right, n, k);

    if (d >= 0) {
      d++;
      if (d == k) {
        printf("%d", t->el);  
      }
      else {
        printNodes(t->left, k - d - 1);  
      }
      return d;
    }
  }

  return -1;
}

/*
  Example Tree:

          1
       /    \
      2      3
     / \    /  \
    4   5  6    7
   /     \     / 
  8       9   10

*/

Tree newTree() 
{
  TreeNode *root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);
  root->left->left = new TreeNode(4);
  root->left->right = new TreeNode(5);
  root->right->left = new TreeNode(6);
  root->right->right = new TreeNode(7);
  root->left->left->left = new TreeNode(8);
  root->left->right->right = new TreeNode(9);
  root->right->right->left = new TreeNode(10);

  return root;
}

int main(int argc, char const *argv[])
{
  Tree t  = newTree();
  printNodes(t, t->left->right->right, 4); //prints nodes which are 4 distance away from 9  which are (8, 3)
  printf("\n");
  printNodes(t, t, 3); //prints nodes which are 3 distance away from 1  which are (8, 9, 10)
  printf("\n");
  printNodes(t, t->left->right, 4); //prints nodes which are 4 distance away from 5  which are (6, 7)
  printf("\n");
  return 0;
}