Archive

Tag Archives: binary

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

Given a number, find the number of 1 in the number’s binary expression. For example, binary express of 10 is 1010. So the number of 1 in it is 2.

Solution

To solve this, we can check each bit by shifting the bits one by one.

1. 1010 -> check 0
2. 101 -> check 1
3. 10 -> check 0
4. 1 -> check 1

So how to check it? we could use the AND function.

1. 1010 -> check 1010 & 1 = 0
2. 101 -> check 101 & 1 = 1 -> counter + 1
3. 10 -> check 10 & 1 = 0
4. 1 -> check 1 & 1 = 1 -> counter + 1

However, negative number will put this program into infinite loop. For example, shifting -10 (0xFFFFFFF6) several times gives 0xFFFFFFFF. Then shifting 0xFFFFFFFF will give 0xFFFFFFFF and makes infinite loops. Therefore instead of shifting the inputting number, we should shift the comparing number.

1. 1010 -> check 1010 & 1 = 0
2. 1010-> check 1010 & 10 = 1 -> counter + 1
3. 1010 -> check 1010 & 100 = 0
4. 1010 -> check 1010 & 1000 = 1 -> counter + 1

Sample

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);
}
%d bloggers like this: