Archive

Tag Archives: tree

Question

Design an algorithm to verify that a tree is a universal value binary tree. Universal value binary tree means all value in that tree is the same.

Solution

There is two approach for this problem. One is with recursive function and another is with iterative function. For this problem, iterative function makes simpler answer. However, we have to learn using recursive function because in production code recursive function uses memory more efficiently while compared to iterative function.

Sample

# node structure
class Node:
    value = None
    left = None
    right = None

    # constructor
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# iterative way to solve this problem
def iteratively_verify_universal_value_binary_tree(root):
    stack = [root]
    while len(stack) > 0:
        node = stack.pop()
        if node.value != root.value: return False
        if node.left: stack.append(node.left)
        if node.right: stack.append(node.right)
    return True

# recursive method to solve this problem
def recursively_verify_universal_value_binary_tree(node, root_value=None):
    if not node: return True
    if not root_value: root_value = node.value  # set root value to compared with
    left_is_universal = recursively_verify_universal_value_binary_tree(node.left, root_value)  # get left result
    right_is_universal = recursively_verify_universal_value_binary_tree(node.right, root_value)  # get right result
    this_is_universal = node.value == root_value  # get this result
    return left_is_universal and right_is_universal and this_is_universal  # combine result

# trees
universal_value_tree = Node(1, Node(1, Node(1), Node(1)), Node(1, Node(1), Node(1)))
non_universal_value_tree = Node(1, Node(1, Node(1), Node(2)), Node(1, Node(1), Node(1)))

# testing
print iteratively_verify_universal_value_binary_tree(universal_value_tree)  # true
print iteratively_verify_universal_value_binary_tree(non_universal_value_tree)  # false
print recursively_verify_universal_value_binary_tree(universal_value_tree)  # true
print recursively_verify_universal_value_binary_tree(non_universal_value_tree)  # false

 

Question

Verify whether all nodes have the same value in a binary tree.

Solution

We can traverse the tree with our usual way, like depth-first or breadth-first algorithm. Then pass a value, probably the root value, to compare with the visiting node.

Example

# node structure
class bst_node:
    value = None
    left = None
    right = None
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# what to do while visiting the node
def visit(node, value):
    return node.value == value

# reflect a binary tree
def depth_first_traversal(root):
    stack = [root]
    value = root.value
    result = True
    while len(stack) > 0:
        node = stack.pop()
        result = visit(node, value)
        if result == False: break
        if node.left: stack.append(node.left)
        if node.right: stack.append(node.right)
    return result

# a binary tree with all values to be 1
node_05 = bst_node(1)
node_07 = bst_node(1)
node_09 = bst_node(1)
node_11 = bst_node(1)
node_06 = bst_node(1, node_05, node_07)
node_10 = bst_node(1, node_09, node_11)
node_08 = bst_node(1, node_06, node_10)

# main
root = node_08
print depth_first_traversal(root)

Question

Print a binary tree layer-by-layer from top to bottom, and from left to right for each layer.

Solution

Yes, it’s a simple task. We can use breadth-first search, and which means we need a queue, see reference.

levelorder(root)
    q = empty queue
    q.enqueue(root)
    while not q.empty do
        node := q.dequeue()
        visit(node)
        if node.left ≠ null then
            q.enqueue(node.left)
        if node.right ≠ null then
            q.enqueue(node.right)

Example

# node structure
class bst_node:
    value = None
    left = None
    right = None
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# what to do with a node.
def visit(node):
    print node.value,

# bfs traversal
def breadth_first_traversal(root):
    queue = [root]
    while len(queue) > 0:
        node = queue.pop(0) # get the head item
        visit(node)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)

# a binary tree and display how was it before reflection
node_05 = bst_node(5)
node_07 = bst_node(7)
node_09 = bst_node(9)
node_11 = bst_node(11)
node_06 = bst_node(6,  node_05, node_07)
node_10 = bst_node(10, node_09, node_11)
node_08 = bst_node(8,  node_06, node_10)

# answer should be: 8 6 10 5 7 9 11
root = node_08
breadth_first_traversal(root)

Question

Construct 2 algorithms to make mirror image of any binary tree inputs, one of them using recursive method, another one using looping method. Mirror image means a binary tree that is the horizontal reflection of the original tree.

Solution

First, to do it in recursive method, we can perform pre-order traversal as usual, see preference. Then swap the left and right children for every node.

reflect(node)
  if node is null then return
  swap(node.left, node.right)
  if node.left is not null then reflect(node.left)
  if node.right is not null then reflect(node.right)

Second, to do it in looping method, we can make use of a stack. Put root node in the stack first. Then in a while-loop, as long as the stack isn’t empty, swap its children. Then put the children nodes into the stack.

reflect(root)
  if root is null then return
  stack.push(root)
  while stack is not empty, do
    node = stack.pop()
    swap(node.left, node.right)
    if node.left is not null then reflect(node.left)
    if node.right is not null then reflect(node.right)

Example

# node structure
class bst_node:
    value = None
    left = None
    right = None
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# swap node's children while visiting
def visit(node):
    temp = node.left
    node.left = node.right
    node.right = temp

# reflect a binary tree
def depth_first_traversal(node):
    if not node: return
    visit(node)
    if node.left: depth_first_traversal(node.left)
    if node.right: depth_first_traversal(node.right)

# debug function to print tree
def print_tree(node, indent=''):
    print "%s-%s" % (indent, node.value)
    if node.left: print_tree(node.left, indent + '  ')
    if node.right: print_tree(node.right, indent + '  ')

# a binary tree and display how was it before reflection
node_05 = bst_node(5)
node_07 = bst_node(7)
node_09 = bst_node(9)
node_11 = bst_node(11)
node_06 = bst_node(6,  node_05, node_07)
node_10 = bst_node(10, node_09, node_11)
node_08 = bst_node(8,  node_06, node_10)
root = node_08
print_tree(root)

# do reflection
depth_first_traversal(root)
print_tree(root)
# node structure
class bst_node:
    value = None
    left = None
    right = None
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# what to do in a loop, here swap the children
def visit(node):
    temp = node.left
    node.left = node.right
    node.right = temp

# reflect a binary tree
def depth_first_traversal(root):
    if not root: return
    stack = [root]
    while len(stack) > 0:
        node = stack.pop()
        visit(node)
        if node.left: stack.append(node.left)
        if node.right: stack.append(node.right)

# debug function to print tree
def print_tree(node, indent=''):
    print "%s-%s" % (indent, node.value)
    if node.left: print_tree(node.left, indent + '  ')
    if node.right: print_tree(node.right, indent + '  ')

# a binary tree and display how was it before reflection
node_05 = bst_node(5)
node_07 = bst_node(7)
node_09 = bst_node(9)
node_11 = bst_node(11)
node_06 = bst_node(6,  node_05, node_07)
node_10 = bst_node(10, node_09, node_11)
node_08 = bst_node(8,  node_06, node_10)
root = node_08
print_tree(root)

# do reflection
depth_first_traversal(root)
print_tree(root)
struct BSTreeNode // a node in the binary search tree (BST)
{
  int m_nValue; // value of node
  BSTreeNode *m_pLeft; // left child of node
  BSTreeNode *m_pRight; // right child of node
};
//就是递归翻转树,有子树则递归翻转子树。
//July、2010/10/19

void Revertsetree(list *root)
{
    if(!root)
       return;
    list *p;

    p=root->leftch;
    root->leftch=root->rightch;
    root->rightch=p;

    if(root->leftch)
      Revertsetree(root->leftch);
    if(root->rightch)
      Revertsetree(root->rightch);
}
void Revertsetree(list *phead)
{
    if(!phead)
       return;

    stack<list*> stacklist;
    stacklist.push(phead);         //首先把树的头结点放入栈中。

    while(stacklist.size())
    //在循环中,只要栈不为空,弹出栈的栈顶结点,交换它的左右子树
    {
      list* pnode=stacklist.top();
      stacklist.pop();

      list *ptemp;
      ptemp=pnode->leftch;
      pnode->leftch=pnode->rightch;
      pnode->rightch=ptemp;

      if(pnode->leftch)
        stacklist.push(pnode->leftch);   //若有左子树,把它的左子树压入栈中
      if(pnode->rightch)
        stacklist.push(pnode->rightch);  //若有右子树,把它的右子树压入栈中
    }
}

Reference

Pre-order Tree Transversal (Wikipedia)

9Question

Get the greatest distance between two nodes in a binary tree. Assume links between nodes are bidirectional. Distance is defined as the amount of nodes connected along the path linked two nodes. Write an algorithm to calculate distance between two nodes. Take the figure at the right, the greatest length should be 4.

Solution

Usual post-order recursive binary tree traversal should do the job. In this case, (obviously) the path must passes through the root. So we should do the following. Recursively return the max length (from left or right) to the parent, and make an exception for the root. The result is simply the sum of maxes from left and right.

Example

# node structure
class bst_node:
    left = None
    right = None
    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

# join left and right max at root, literally
def get_max_len(root):
    left_max = depth_first_traversal(root.left)
    right_max = depth_first_traversal(root.right)
    return left_max + right_max

# a usual traversal, returning the max length begin
# from this node
def depth_first_traversal(node):
    if not node: return 0
    left_max = depth_first_traversal(node.left)
    right_max = depth_first_traversal(node.right)
    return max(left_max, right_max) + 1

# binary tree setup
node_12 = bst_node()
node_13 = bst_node()
node_05 = bst_node()
node_07 = bst_node(node_12, node_13)
node_09 = bst_node()
node_11 = bst_node()
node_06 = bst_node(node_05, node_07)
node_10 = bst_node(node_09, node_11)
node_08 = bst_node(node_06, node_10)

# answer should be 5
root = node_08
print get_max_len(root)
# node structure
class bst_node:
    left = None
    right = None
    left_max_dist = 0
    right_max_dist = 0

    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

    def max_dist(self):
        return max(self.left_max_dist, self.right_max_dist)

# calculate function
def calculate_max_len(node):

    # check node
    if not node: return 0

    # if left is not empty, then left is is the max + 1
    if node.left:
        calculate_max_len(node.left)
        node.left_max_dist = node.left.max_dist() + 1

    # if right is not empty, right is is the max + 1
    if node.right:
        calculate_max_len(node.right)
        node.right_max_dist = node.right.max_dist() + 1

    # return the max dist
    return node.left_max_dist + node.right_max_dist

# bst
node_12 = bst_node()
node_13 = bst_node()
node_5 = bst_node()
node_7 = bst_node(node_12, node_13)
node_9 = bst_node()
node_11 = bst_node()
node_6 = bst_node(node_5, node_7)
node_10 = bst_node(node_9, node_11)
node_8 = bst_node(node_6, node_10)

# answer should be 5
root = node_8
print calculate_max_len(root)
// 数据结构定义
struct NODE
{
     NODE* pLeft;            // 左子树
     NODE* pRight;          // 右子树
     int nMaxLeft;          // 左子树中的最长距离
     int nMaxRight;         // 右子树中的最长距离
     char chValue;        // 该节点的值
};

int nMaxLen = 0;

// 寻找树中最长的两段距离
void FindMaxLen(NODE* pRoot)
{
     // 遍历到叶子节点,返回
     if(pRoot == NULL) {
          return;
     }
     // 如果左子树为空,那么该节点的左边最长距离为0
     if(pRoot -> pLeft == NULL) {
          pRoot -> nMaxLeft = 0;
     }
     // 如果右子树为空,那么该节点的右边最长距离为0
     if(pRoot -> pRight == NULL) {
          pRoot -> nMaxRight = 0;
     }
     // 如果左子树不为空,递归寻找左子树最长距离
     if(pRoot -> pLeft != NULL) {
          FindMaxLen(pRoot -> pLeft);
     }
     // 如果右子树不为空,递归寻找右子树最长距离
     if(pRoot -> pRight != NULL) {
          FindMaxLen(pRoot -> pRight);
     }
     // 计算左子树最长节点距离
     if(pRoot -> pLeft != NULL) {
          int nTempMax = 0;
          if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight) {
               nTempMax = pRoot -> pLeft -> nMaxLeft;
          }
          else {
               nTempMax = pRoot -> pLeft -> nMaxRight;
          }
          pRoot -> nMaxLeft = nTempMax + 1;
     }
     // 计算右子树最长节点距离
     if(pRoot -> pRight != NULL) {
          int nTempMax = 0;
          if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight) {
               nTempMax = pRoot -> pRight -> nMaxLeft;
          }
          else {
               nTempMax = pRoot -> pRight -> nMaxRight;
          }
          pRoot -> nMaxRight = nTempMax + 1;
     }
     // 更新最长距离
     if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen) {
          nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;
     }
 }
 //很明显,思路完全一样,但书上给的这段代码更规范!:)。
//定义一个结构体
struct NODE
{
    NODE* pLeft;
    NODE* pRight;
    int MaxLen;
    int MaxRgt;
};
NODE* pRoot;  //根节点
int MaxLength;

void traversal_MaxLen(NODE* pRoot) {
    if(pRoot == NULL) {
        return 0;
    };
    if(pRoot->pLeft == NULL) {
        pRoot->MaxLeft = 0;
    }
    // 若左子树不为空
    else {
        int TempLen = 0;
        // 左子树上的,某一节点,往左边大,还是往右边大
        if(pRoot->pLeft->MaxLeft > pRoot->pLeft->MaxRight) {
            TempLen+=pRoot->pLeft->MaxLeft;
        }
        else {
            TempLen+=pRoot->pLeft->MaxRight;
        }
        pRoot->nMaxLeft = TempLen + 1;
        traversal_MaxLen(NODE* pRoot->pLeft); // 此处,加上递归
    }

    if(pRoot->pRigth == NULL) {
        pRoot->MaxRight = 0;
    }
    // 若右子树不为空
    else {
        int TempLen = 0;
        // 右子树上的,某一节点,往左边大,还是往右边大
        if(pRoot->pRight->MaxLeft > pRoot->pRight->MaxRight) {
            TempLen+=pRoot->pRight->MaxLeft;
        }
        else {
            TempLen+=pRoot->pRight->MaxRight;
        }
        pRoot->MaxRight = TempLen + 1;
        traversal_MaxLen(NODE* pRoot->pRight); // 此处,加上递归
    }

    if(pRoot->MaxLeft + pRoot->MaxRight > 0) {
        MaxLength=pRoot->nMaxLeft + pRoot->MaxRight;
    }
}

9

Question

Construct an algorithm to verify if a set of numbers is the post-order search result of a binary search tree. Let the figure at the right hand side as an example, the algorithm will return true if {5, 7, 6, 9, 11, 10, 8}. However, it will return false if the input is {7, 4, 6, 5}.

Solution

Actually, a post-order search of the whole tree would do the job. First, perform a depth-first search from the leftmost leave, and push each element into a stack.

Reference

Wikipedia

Pseudocode

postorder(node)
    if node == null then return
    postorder(node.left)
    postorder(node.right)
    visit(node)

Samples

class bst_node:
    value = None
    left = None
    right = None
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def postorder(node, test_seq):
    if node is None: return True
    if not postorder(node.left, test_seq): return False
    if not postorder(node.right, test_seq): return False
    return visit(node, test_seq)

def visit(node, test_seq):
    front = test_seq.pop(0) # front item
    return front == node.value

node_5 = bst_node(5)
node_7 = bst_node(7)
node_9 = bst_node(9)
node_11 = bst_node(11)
node_6 = bst_node(6, node_5, node_7)
node_10 = bst_node(10, node_9, node_11)
node_8 = bst_node(8, node_6, node_10)
root = node_8

test_seq_1 = [5, 7, 6, 9, 11, 10, 8]
test_seq_2 = [7, 4, 6, 5]

print postorder(root, test_seq_1)
print postorder(root, test_seq_2)
bool verifySquenceOfBST(int squence[], int length)
{
      if(squence == NULL || length <= 0)
            return false;

      // root of a BST is at the end of post order traversal squence
      int root = squence[length - 1];

      // the nodes in left sub-tree are less than the root
      int i = 0;
      for(; i < length - 1; ++ i)
      {
            if(squence[i] > root)
                  break;
      }

      // the nodes in the right sub-tree are greater than the root
      int j = i;
      for(; j < length - 1; ++ j)
      {
            if(squence[j] < root)
                  return false;
      }

      // verify whether the left sub-tree is a BST
      bool left = true;
      if(i > 0)
            left = verifySquenceOfBST(squence, i);

      // verify whether the right sub-tree is a BST
      bool right = true;
      if(i < length - 1)
            right = verifySquenceOfBST(squence + i, length - i - 1);

      return (left && right);
}

Questiontree

Convert binary search tree into doubly linked list. It’s required not to create any new node, but only turning pointers.

Solution

The following shows the concept of this question.

        8
      /   
    6       0       ->     5 = 6 = 7 = 8 = 9 = 0 = 1
   /      / 
  5   7   9    1

First, since node for both binary tree and doubly linked list have left and right node, they can use the same node structure. Then, looking the doubly linked list as a normal linked list, it is actually a in-order depth-first traversal result.

Sample Codes

 

# node structure
class Node:
    value = None
    left = None
    right = None

    # constructor
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# what to do with a node.
def visit(node):
    global node_temp
    global node_root
    if not node_temp: node_root = node  # head
    else: node_temp.right = node  # make right of temp to this
    node.left = node_temp  # make temp to this left
    node_temp = node  # next node

# bfs traversal
def depth_first_recursive_traversal_in_order(node):
    if node is None: return
    depth_first_recursive_traversal_in_order(node.left)
    visit(node)
    depth_first_recursive_traversal_in_order(node.right)

# a binary tree and display how was it before reflection
node_5 = Node(5)
node_7 = Node(7)
node_9 = Node(9)
node_1 = Node(1)
node_6 = Node(6, node_5, node_7)
node_0 = Node(0, node_9, node_1)
node_8 = Node(8, node_6, node_0)

# conversion
node_root = node_8
node_temp = None
depth_first_recursive_traversal_in_order(node_root)

# answer should be: 5 6 7 8 9 0 1
node_temp = node_root
while node_temp:
    print node_temp.value,
    node_temp = node_temp.right
public class InterviewPractice1
{
    // global
    static Node node_root = null;
    static Node node_temp = null;

    // node structure
    private static class Node
    {
        private int value;
        private Node left;
        private Node right;

        public Node(int value, Node left, Node right)
        {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    // visit
    private static void visit(Node node)
    {
        if (node_temp == null) node_root = node; // set head
        else node_temp.right = node; // make right of temp to this node
        node.left = node_temp; // make temp to the left of this node
        node_temp = node; // next node

    }

    // depth first, recursive
    private static void depth_first_recursive_traversal_in_order(Node node)
    {
        if (node == null) return;
        depth_first_recursive_traversal_in_order(node.left);
        visit(node);
        depth_first_recursive_traversal_in_order(node.right);
    }

    // main
    public static void main(String[] args)
    {
        // tree
        Node node_5 = new Node(5, null, null);
        Node node_7 = new Node(7, null, null);
        Node node_9 = new Node(9, null, null);
        Node node_1 = new Node(1, null, null);
        Node node_6 = new Node(6, node_5, node_7);
        Node node_0 = new Node(0, node_9, node_1);
        Node node_8 = new Node(8, node_6, node_0);

        // run
        node_root = node_8;
        depth_first_recursive_traversal_in_order(node_root);

        // the result should be 5 6 7 8 9 0 1
        node_temp = node_root;
        while (node_temp != null) {
            System.out.print(node_temp.value + " ");
            node_temp = node_temp.right;
        }
    }
}
#include <iostream>

struct Node
{
    int value;
    Node *left;
    Node *right;

    Node(int value, Node *left = NULL, Node *right = NULL)
    {
        this->value = value;
        this->left = left;
        this->right = right;
    }
};

Node *node_root = NULL;
Node *node_temp = NULL;

void visit(Node *node)
{
    if (node_temp == NULL) node_root = node;  // set head
    else node_temp->right = node;  // make right of them to this node
    node->left = node_temp;  // make temp to the left of this node
    node_temp = node;  // next node
}

void depth_first_recursive_traversal_in_order(Node *node)
{
    if (!node) return;
    depth_first_recursive_traversal_in_order(node->left);
    visit(node);
    depth_first_recursive_traversal_in_order(node->right);
}

int main()
{
    // tree
    Node *node_5 = new Node(5);
    Node *node_7 = new Node(7);
    Node *node_9 = new Node(9);
    Node *node_1 = new Node(1);
    Node *node_6 = new Node(6, node_5, node_7);
    Node *node_0 = new Node(0, node_9, node_1);
    Node *node_8 = new Node(8, node_6, node_0);

    // conversion
    node_root = node_8;
    node_temp = NULL; // null
    depth_first_recursive_traversal_in_order(node_8);

    // answer should be: 5 6 7 8 9 0 1
    node_temp = node_root;
    while (node_temp) {
        printf("%d ", node_temp->value);
        node_temp = node_temp->right;
    }
}
%d bloggers like this: