Binary Trees

Binary Trees

• Binary tree is data structure in which each node contains maximum of two children

• Binary search tree same as binary tree but sorted.

Check whether given TREE is BST

is_bst.python

In [2]: # Node definition
   ...: class Node:
   ...:     def __init__(self, value, left=None, right=None):
   ...:         self.value = value
   ...:         self.left  = left
   ...:         self.right = right
   ...:     def __str__(self):
   ...:         return str(self.value)
   ...:

In [3]: #define function to check given tree is binary search tree
   ...: #BST is a tree whose left.node.value<node.value and node.value<right.node.value
   ...: def is_bst(node, rnp_value = None, lnp_value = None):
   ...:     # if node.value < right.node.parent.value
   ...:     if rnp_value and node.value < rnp_value:
   ...:         return False
   ...:     # if  node.value > left.node.parent.value
   ...:     if lnp_value and node.value > lnp_value:
   ...:         return False
   ...:     is_left_bst = True
   ...:     is_right_bst = True
   ...:
   ...:     if node.left:# check if left tree is BST
   ...:         is_left_bst = is_bst(node.left, lnp_value = node.value)
   ...:     if node.right:# check if right tree is BST
   ...:         is_right_bst = is_bst(node.right, rnp_value = node.value)
   ...:
   ...:     return is_left_bst and is_right_bst
   ...:

In [4]: root_node =Node(1,Node(3), Node(2))

In [5]: is_bst(root_node)
Out[5]: False

In [6]: root_node =Node(2,Node(1), Node(3))

In [7]: is_bst(root_node)
Out[7]: True

In [10]: root_node =Node(3,Node(1,Node(0), Node(2)), Node(4, Node(5), Node(6)))

In [11]: is_bst(root_node)
Out[11]: False

In [12]: root_node =Node(3,Node(1,Node(0), Node(2)), Node(5, Node(4), Node(6)))

In [13]: is_bst(root_node)
Out[13]: True

elucidation /əˌlo͞osəˈdāSH(ə)n/

1. create node definition using Node class

2. create a function called is_bst which takes (node, left_node_parent_value, right_node_parent_value)

pseudo

is_bst(node, left_node_value, right_node_value):

IF left_node_value < it_parent && right_node_value > its_parent

    left_bst = is_bst(node.left, left_node_value)

    right_bst = is_bst(node.right, right_node_value)

    return left_bst & right_bst

Lowest Common Ancestor

lca.python

In [11]: class Node:
    ...:     def __init__(self, value, left=None, right=None):
    ...:         self.value = value
    ...:         self.left = left
    ...:         self.right = right
    ...:
    ...:     def __repr__(self):
    ...:         return str(self.value)
    ...:
    ...:     def __eq__(self, other):
    ...:         if type(other) is type(self):
    ...:             return other.value == self.value
    ...:         return False
    ...:
    ...:     def __hash__(self):
    ...:         return self.value

path_to_x.python

In [12]: def path_to_x(root, x):
    ...:     if not root: # root is None return None( no path to x)
    ...:         return None
    ...:     if root.value == x: # prepare path from this element back to root
    ...:         return [root]
    ...:
    ...:     left_path = path_to_x(root.left, x)
    ...:     if left_path:
    ...:         left_path.append(root)# recruisvely accumulate path till root
    ...:         return left_path
    ...:
    ...:     right_path = path_to_x(root.right, x)
    ...:     if right_path:
    ...:         right_path.append(root)# recursevly accumulate path till root
    ...:         return right_path
    ...:     # if these is no valid path return empty path
    ...:
    ...:     return []

lca.python

In [16]: def lca(root, j, k):
    ...:     path_to_j = path_to_x(root, j)
    ...:     path_to_k = path_to_x(root, k)
    ...:
    ...:     lca = None
    ...:
    ...:     while path_to_j and path_to_k:
    ...:         j = path_to_j.pop()
    ...:         k = path_to_k.pop()
    ...:         if j == k:
    ...:             lca =j # or k
    ...:         else:
    ...:             break
    ...:     return lca

Last updated 2018-11-17 18:02:13 EST