Chapter 4 Trees and Graphs - 4.5
Problem 4.5: Write an algorithm to find the 'next' node (i.e., in-order successor) of a given node in a binary search tree where each node has a link to its parent.
To address this problem, the most important thing is making the cases clear. The three cases we should consider about are:
1) The given node has right child.
2) The given node has no right child.
a. The given node is the left child of its parent.
b. The given node is the right child of its parent.
The implementation is given below:
from queue import *class btree_node: def __init__(self, value = None, parent = None): self.value = value self.parent = parent self.left = None self.right = Nonedef find_next_node(node): if node == None: return None # If the given node has right child if node.right != None: # Find the next node in right branch next = node.right while next.left != None: next = next.left return next # If the given node has no right child # and it is left child of its parent elif node == node.parent.left: return node.parent # If the given node has no right child # and it is right child of its parent elif node == node.parent.right: # The given node is the greatest in the sub-tree, # whose root is the given node's parent. # The sub-tree above is left sub-tree of a node, # and the node is next node of given node next = node.parent while next != None: if (next.parent == None) or (next == next.parent.left): break else: next = next.parent if next == None: return None else: return next.parent# Test caseif __name__ == "__main__": # Construct the binary search tree array = [btree_node(i) for i in range(0, 15)] root = construct_min_btree(array, 0, 14) # Print the binary tree in level-order q = queue() q.enqueue(root) current_level = 0 num_in_current_level = 2**current_level while not q.is_empty(): n = q.dequeue() print n.value, if n.left != None: q.enqueue(n.left) if n.right != None: q.enqueue(n.right) num_in_current_level -= 1 # End of a level if num_in_current_level == 0: current_level += 1 num_in_current_level = 2**current_level print "\n" # Test the implementation print find_next_node(array[0]).value# Utility function to construct binary search treedef construct_min_btree(array, start, end): if start > end: return None mid = (start + end)/2 array[mid].left = construct_min_btree(array, start, mid - 1) array[mid].right = construct_min_btree(array, mid + 1, end) if array[mid].left != None: array[mid].left.parent = array[mid] if array[mid].right != None: array[mid].right.parent = array[mid] return array[mid]
