Lets solve another exercise from the Trees and Graphs chapter and write some nice python code.
Here it is:
4.6 Design an algorithm and write code to find the first common ancestor of two nodes
in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not
necessarily a binary search tree.
Let’s write a test
First, lets create a tree and write a test. I don’t feel like creating a tree by hand so I’ll write a function to create a full binary tree for a given number of levels.
Let’s keep a simple representation of a tree:
class TreeNode: def __init__(self, data, left=None, right=None): self.data=data self.left=left self.right=right
Now let’s write a function to create a tree. We need a unique name for each node, I’ll use a global variable for this purpuse.
def constructTree(levels, level=0): global total if level==levels: return None total+=1 newNode = TreeNode('node ' + `level`+"_"+`total`); newNode.left=constructTree(levels,level+1) newNode.right=constructTree(levels,level+1) return newNode def get_node(head, name): "returns the first node with the given name" if not head: return None if (head.data==name): return head left = get_node(head.left, name) if left: return left return get_node(head.right, name)
For convenience, I also wrote a method to get a node by its name so I can easily write my tests.
Here they are:
global total total = 0 t = constructTree(5) n1=get_node(t,'node 4_27') n2=get_node(t,'node 3_19') assert(firstAncestor(t,n1,n2).data=='node 1_17') n1=get_node(t,'node 2_18') n2=get_node(t,'node 4_16') assert(firstAncestor(t,n1,n2).data=='node 0_1')
The tree I build for the test looks like this:
'node 0_1' 'node 1_2' 'node 2_3' 'node 3_4' 'node 4_5' 'node 4_6' 'node 3_7' 'node 4_8' 'node 4_9' 'node 2_10' 'node 3_11' 'node 4_12' 'node 4_13' 'node 3_14' 'node 4_15' 'node 4_16' 'node 1_17' 'node 2_18' 'node 3_19' 'node 4_20' 'node 4_21' 'node 3_22' 'node 4_23' 'node 4_24' 'node 2_25' 'node 3_26' 'node 4_27' 'node 4_28' 'node 3_29' 'node 4_30' 'node 4_31'
The idea is to start from the head and traverse the graph level by level. At each step we will ask: is the current node the first common ancestor ?
It is if and only if the two nodes are located on left and right side of the current node. We will need a function to test if a node is contained in a given tree:
def containsNode(node,needle): if not node: return False if node==needle: return True return containsNode(node.left, needle) or containsNode(node.right, needle)
And now the function to find the first ancestor. Starting with the head, we use containsNode() function to test if the two nodes are located on left and right of the current node:
def firstAncestor(current, node1, node2): #special case: node1 first ancestor of node2 or viceversa if containsNode(node1, node2): return node1 if containsNode(node2, node1): return node2 if not current: return None n1_left = containsNode(current.left, node1); n2_left = containsNode(current.left, node2); if (n1_left or n2_left) and not (n1_left and n2_left): return current if n1_left: return firstAncestor(current.left, node1,node2) else: return firstAncestor(current.right, node1, node2)
So what’s the complexity of this algorithm ? I would guess n*log(n) given the fact that I traverse the tree (with firstAncestor function) and, for each node, I traverse the tree having that node as head (with containsNode function). In my previous post we so this traversal was O(n*log(n))
Well, I think I should pay more attention to the complexity.
Let’s count again the operations:
– firstAncestor() visits first node. It calls containsNode() twice for the left tree. Which gives us 2*n/2 operations. Then it goes to either left or right, dividing the remaining number of nodes by two, which gives us:
n + n/2 + n/4 + … operations = n (1 + 1/2 + 1//4 … ) which is upper bounded by 2n (see geometric serries ).
This gives us O(n)
Second and Best Solution
The idea is simple: for each of the two nodes we will find the path of nodes that leads from the head to the given node. Then we only need to put the 2 paths next to each other and see the common ancestor:
def path_to_node(current, needle, nodes=None): if nodes==None: nodes= if not current: return None buff=nodes[:] if current==needle: buff = [current] return buff left = path_to_node(current.left, needle, buff) if left: buff = [current] + left return buff right = path_to_node(current.right, needle, buff) if right: buff = [current] + right return buff def firstAncestorOptimized(head, node1, node2): l1 = path_to_node(head,node1) l2 = path_to_node(head,node2) k=0 while l1[k]==l2[k]: k=k+1 if k==0: return None return l1[k-1]
For me it looks like O(n).
That’s all for today.