recursive solution for tree programs

kumaya · kumaya · commit 75d02bfe2845 · 2017-08-30T23:35:32.000+05:30
diff --git a/LinkedList/doubly_linked_list_c_k.py b/LinkedList/doubly_linked_list_c_k.py
@@ -45,8 +45,10 @@ def revDLL(head):
 def modify(h, c, k):
     final = h
     data = k - c
+    # insert new node if required
     while h:
         if data == h.data:
+            # if node with value==data already exists, do nothing
             break
         if data > h.data:
             h = h.n
@@ -62,7 +64,8 @@ def modify(h, c, k):
             break
     while h:
         if k == h.data:
-            h.prev.n = h.n
+            if h.prev:
+                h.prev.n = h.n
             if h.n:
                 h.n.prev = h.prev
         h = h.n
@@ -80,9 +83,9 @@ def modify(h, c, k):
     head.n.n.n.n = NodeDLL(10)
     head.n.n.n.n.prev = head.n.n.n
     print "Original DLL: ", printDLL(head)
-    print "Original Reversed DLL: ", revDLL(head.n.n.n.n)
-    k = 9
-    c = 5
+    # print "Original Reversed DLL: ", revDLL(head.n.n.n.n)
+    k = 2
+    c = 0
     nh = modify(head, c, k)
     print "Modified DLL: ", printDLL(nh)
-    print "Reversed DLL: ", revDLL(nh.n.n.n.n)
+    # print "Reversed DLL: ", revDLL(nh.n.n.n.n)
diff --git a/TreeADT/pair_with_sum_bst.py b/TreeADT/pair_with_sum_bst.py
@@ -54,6 +54,27 @@ def get_pair_with_sum(root, target):
             return False
 
 
+def get_pair_with_sum_rec(root, node, val):
+    if not node:
+        return False
+    orignl_root = root
+    diff = val - node.data
+    if has_other_pair(orignl_root, node, diff):
+        first_part = val - diff
+        return first_part, diff
+    return get_pair_with_sum_rec(orignl_root, node.left, sum) or \
+           get_pair_with_sum_rec(orignl_root, node.right, sum)
+
+
+def has_other_pair(root, this_node, rem):
+    if not root:
+        return
+    if root.data == rem and this_node!=root:
+        return root.data
+    elif root.data < rem:
+        return has_other_pair(root.right, this_node, rem)
+    elif root.data > rem:
+        return has_other_pair(root.left, this_node, rem)
 
 if __name__ == "__main__":
     root = BSTNode(4)
@@ -67,5 +88,7 @@ def get_pair_with_sum(root, target):
     root.right.left = BSTNode(5)
     root.right.right = BSTNode(7)
 
-    sum = 8
-    print get_pair_with_sum(root, sum)
+    sum = 4
+    for sum in xrange(1, 15):
+        print get_pair_with_sum(root, sum),
+        print get_pair_with_sum_rec(root, root, sum)
