Reverse level order traversal of a tree given in an array form

Probelm:

One of the many ways of representing a tree is to have an array(of length same as number of nodes), where each element in the node denotes the parent of that node.
Please note –
* An element with parent = -1 is the root element.
* An element with the least index becomes the left most child. (ie. a node with always be on left of all its siblings that have higher index than it)
* When printing a level of tree you need to maintain left to right order.
Eg –
{-1, 0, 0, 1, 1} would represent a tree with –
* 0 as root
* 1 and 2 as children of 0
* 3 and 4 as children of 1

Given a similar representation, you have to print reverse level order traversal of the corresponding tree.
Level order traversal of a tree is where we traverse levels of tree one by one.

Eg –
For the above given tree, level order traversal would be –
0
1 2
3 4
And hence, the reverse level order traversal is –
3 4
1 2
0

Solution:


#!/usr/bin/env python

n = raw_input()
tree = raw_input().split()

#Inverse the tree
parent = {} 

for idx, val in enumerate(tree):
  if val in parent:
    parent[val].append(str(idx))
  else:
    parent[val] = [str(idx)]

#BFT of the tree
def bft (q, t):
  if len(q) == 0: return
  ret = q
  q = []
  for node in ret:
    if node in t:
      q += t[node]
  bft(q, t)
  print " ".join(ret) 

bft(parent['-1'], parent)

Vertical Order traversal of a tree from the bottom

#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

#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

#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;
}

Inplace binary tree from spiral order traversal given in a doubly linked list

/* 
Example:

Spiral order traversal:
1-2-3-4-5-6-7-8

Tree:
            1
         /    \
       3       2
     /  \    /   \
   4     5  6     7
                   \
                    8

Algorithm:
  Using deque, push in one end and pop from other end, when the level 
  changes, change the directions of push and pop
*/

#include <cstdio>
#include <deque>

struct DoublyLinkedListNode
{
  int el;
  DoublyLinkedListNode *left;
  DoublyLinkedListNode *right;

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

typedef DoublyLinkedListNode* DoublyLinkedList;
typedef DoublyLinkedListNode* Tree;

struct DequeNode
{
  DoublyLinkedListNode *dlNode;
  int level;

  DequeNode(DoublyLinkedListNode *_dlNode, int _level) : 
                      dlNode(_dlNode), level(_level) {}
};

void spiralDoublyLinkedList2BinaryTree(DoublyLinkedList d) 
{
  if (!d) return;

  std::deque<DequeNode> q;

  q.push_back(DequeNode(d, 0));

  DoublyLinkedListNode *right, 
                       *left,
                       *iter = d;

  bool rightToLeft = true;

  int currentLevel = 0;

  while(!q.empty()) {

    DequeNode dqNode = rightToLeft ? q.back() : q.front();

    if (dqNode.level != currentLevel) {
      rightToLeft = !rightToLeft;
      dqNode = rightToLeft ? q.back() : q.front();
      currentLevel = dqNode.level;    
    }

    if (rightToLeft) {
      q.pop_back();
    } else {
      q.pop_front();
    }

    DoublyLinkedListNode *tmpDlNode = dqNode.dlNode;

    if (iter == NULL) {
      tmpDlNode->right = tmpDlNode->left = NULL;
    } else {

      left = iter->right;
      right = left ? left->right : NULL;

      if (rightToLeft) {
        tmpDlNode->left = right;
        tmpDlNode->right = left;

        if (left) {
          q.push_front(DequeNode(left, currentLevel + 1));
        }

        if (right) {
          q.push_front(DequeNode(right, currentLevel + 1));
        }

      } else {

        tmpDlNode->left = left;
        tmpDlNode->right = right;

        if (left) {
          q.push_back(DequeNode(left, currentLevel + 1));
        }

        if (right) {
          q.push_back(DequeNode(right, currentLevel + 1));
        }
      }

      iter = right;
    }
  }
}

void spiralOrderTraversal(Tree t)
{
  if (!t) return;

  std::deque<DequeNode> q;

  q.push_back(DequeNode(t, 0));

  bool rightToLeft = true ;

  int currentLevel = 0;

  while(!q.empty()) {

    DequeNode dqNode = rightToLeft ? q.back() : q.front();

    if (dqNode.level != currentLevel) {
      rightToLeft = !rightToLeft;
      dqNode = rightToLeft ? q.back() : q.front();
      currentLevel = dqNode.level;    
    }

    if (rightToLeft) {
      q.pop_back();
    } else {
      q.pop_front();
    }

    DoublyLinkedListNode *tmpDlNode = dqNode.dlNode;

    printf("%d", tmpDlNode->el);

    if (rightToLeft) {

      if (tmpDlNode->left) {
        q.push_front(DequeNode(tmpDlNode->left, currentLevel + 1));
      }

       if (tmpDlNode->right) {
        q.push_front(DequeNode(tmpDlNode->right, currentLevel + 1));
      }

    } else {

     if (tmpDlNode->right) {
        q.push_back(DequeNode(tmpDlNode->right, currentLevel + 1));
      }

      if (tmpDlNode->left) {
        q.push_back(DequeNode(tmpDlNode->left, currentLevel + 1));
      }
    }
  }
  printf("\n");

}

DoublyLinkedList makeList(int n) 
{
  DoublyLinkedListNode *d = new DoublyLinkedListNode(1);

  DoublyLinkedListNode *tmpDlNode = d;

  for (int i = 2; i <= n; ++i) {
    tmpDlNode->right = new DoublyLinkedListNode(i);
    tmpDlNode->right->left = tmpDlNode;
    tmpDlNode = tmpDlNode->right;
  }

  return d;
}

void printList(DoublyLinkedList d)
{
  while (d) {
    printf("%d", d->el);
    d = d->right;
  }

  printf("\n");
}

int main(int argc, char const *argv[])
{
  DoublyLinkedList d = makeList(8);

  printf("Before spiralOrderTraversal : ");
  printList(d);
  spiralDoublyLinkedList2BinaryTree(d);

  printf("After  spiralOrderTraversal : ");
  spiralOrderTraversal(d);

  return 0;
}

Print ancestors of a given binary tree node without recursion

#include <stdio.h>
#include <stack>

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

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

typedef TreeNode* Tree;

struct StackNode
{
  TreeNode *node;
  bool visited;

  explicit StackNode(TreeNode *t) : node(t), visited(false) {}

  ~StackNode() {
    delete node;
  }

  private:
  StackNode(const StackNode &);
  StackNode operator=(const StackNode &);


};

void printAncestor(Tree t, int key) 
{
  std::stack<StackNode *> stack;

  if (!t || t->el == key) return;

  stack.push(new StackNode(t));

  TreeNode *tmp = t->left;

  while (!stack.empty()) {

    if (tmp) {

      if (tmp->el == key) {
        //Key found print the ancestors
        while (!stack.empty()) {
          StackNode *s = stack.top();
          printf("%d ", s->node->el);
          stack.pop();
        }
      } else {
        stack.push(new StackNode(tmp));
        tmp = tmp->left;
      }
    } else {
      //Traverse the right subtree, if not traversed
      StackNode *s = stack.top();
      if (!s->visited) {
        s->visited = true;
        tmp = s->node->right;
      } else {
        stack.pop();
      }
    }
  }

}

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();

  for (int i = 1; i <= 11; ++i) {
    printf("%d: ", i);
    printAncestor(t, i);
    printf("\n");
  }
  
  return 0;
}