Skip to content

Instantly share code, notes, and snippets.

@DagnyTagg2013

DagnyTagg2013/Binary Tree - DelNode!

Created November 28, 2017 20:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save DagnyTagg2013/a70d20a372c356389b5ffa969574f3c3 to your computer and use it in GitHub Desktop.
Save DagnyTagg2013/a70d20a372c356389b5ffa969574f3c3 to your computer and use it in GitHub Desktop.
Download ZIP
BinTree - DelNode
Raw
Binary Tree - DelNode!
"""
DELETE node from Binary Tree
CORE CASES:
*** CAREFUL/INTERESTING
-- need to distinguish applicable SIDE(left or right child); INTO TARGET from
PARENT, as well as OUT of TARGET
- target is root => reset root to None
- target has no child; and target is LEFT or RIGHT child of parent
=> reset parent's child (specific side) to None
- target has one child; and target is LEFT or RIGHT child of parent
=> reset parent child (specific side) to child of Target (specific side)
- target two children; and target is LEFT or RIGHT child of parent
=> find ANY LEAF off TARGET, for replacing itself
=> detach THAT leaf, append TARGET's 2 children to it
=> make this the child of the parent (specific side)
to replace TARGET
- empty tree => throw Exception as invalid input
KEY CONCEPTS:
1) FIND/TRAVERSAL, needs to know PARENT to TARGET node to delete WITHOUT Back Pointer, SO, need to traverse via DFS/Stack/Recursion vs BST/Loop
2) need to save TARGET's NEXT ptrs BEFORE deleting TARGET,
then attach PARENT pointers to TARGET'S NEXT
3) TRICKY -- need to distinguish applicable SIDE(left or right child); INTO TARGET from PARENT, as well as OUT of TARGET
4) visit ROOT FIRST to exit FASTEST if target no matched; and don't care about Left or Right since unordered BST => but ORDERED BST would be FASTER O(logN) avg or O(N) worst-case
5) BACKTRACK - LOCAL-REFERENCE-COPIES of RECURSIVE function args;
are POPPED from callstack on exit
6) EXIT THROUGH RECURSION LEVELS - on FOUND node, so return DEEPER results to (new)
vars that don't interfere with calling params
AT LEVEL
SIMPLIFY:
1) differentiate Tree from Node as need to distinguish ROOT vs generic NODE case
2) case for target having 2 children:
- EASIER - not sorted BST, as BIN TREE is UNORDERED!
- so just pick ANY leaf and swap it into the deleted target spot!
- vs for BST
- find IMMEDIATE PREDECESSOR LEAF (right child, then LEFT LEAF)
- move that entire RIGHT subtree to replace deleted node
- CAREFUL to SAVE remaining RIGHT subtree of deleted node;
as this will be attached to RIGHTMOST LEAF of above replacement subtree
3) breakup to code __REPR_, FIND wrapper with RECURSIVE helper; THEN DELNODE
"""
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
class BinTree:
def __init__(self, rootVal=None):
if rootVal:
self.root = Node(rootVal)
else:
self.root = None
# TODO: find out nice way to print tree structure!
def _recurPrint_(self, node, contents):
if node.left:
contents.append("/\n")
self._recurPrint_(node.left, contents)
if node:
contents.append('*{}*\n'.format(node.value))
if node.right:
contents.append("\\\n")
self._recurPrint_(node.right, contents)
return "".join(contents)
# TODO: best way to print output of tree!
# DEBUG: need to PRINT the TREE with MORE than LEVEL info; but BRANCHES
# so RECURSE vs BFS LOOP with sentinel break at each LEVEL!
# ===> SAY INORDER L, ROOT, RIGHT
def __repr__(self):
contents = []
strContents = ""
# ATTN: check for NONE, and also recurse on ROOT!
if self.root:
strContents = self._recurPrint_(self.root, contents)
else:
strContents = "EMPTY"
return strContents
# RECURSION NEEDED!
# DEBUG-TRICKY: we need to know from WHICH branch we got TO the targetNode
# to be able to connect correct branch of the priorNode to SKIP
# it! so use True for is Target LChild, None for ROOT,
# False for RChild
# TODO: could also find out how to do enumeration States!
def findTargetNodeR(self, priorNode, currNode, targetNodeValue, isTargetLChild):
# DEBUG: verifying DEEPER RECURSION CALL local node reference
# print ("ENTRY: prior{}, current{}".format(priorNode, currNode))
# EXIT immediately on FOUND; as no need to go DEEPER
if (currNode.value == targetNodeValue):
# ATTN: Python convenience can return TUPLE!
return (priorNode, currNode, None)
# RECURSE/ITERATE if children exist; down to LEAF Node
if (currNode.left):
priorNodeL, foundTargetL, isTargetLChild = self.findTargetNodeR( \
currNode, currNode.left, targetNodeValue, True)
# DEBUG: verifying DEEPER RECURSION CALL local node reference popped
# print ("RETURNL: prior{}, current{}".format(priorNode, currNode))
# ATTN: if FOUND, then accept (new) DEEP values to FORCE return
# BACK THROUGH MULTIPLE RECURSION LEVELs
# otherwise, ignore DEEP values;
# and retain LEVEL state to allow BACKTRACKING
if ( foundTargetL ):
return (priorNodeL, foundTargetL, True)
else:
# if NOT FOUND, allow further processing-recursion on RIGHT
pass
if (currNode.right):
priorNodeR, foundTargetR, isTargetLChild = self.findTargetNodeR( \
currNode, currNode.right, targetNodeValue, False)
# ATTN: verifying DEEPER RECURSION CALL local node reference popped
# print ("RETURNR: prior{}, current{}".format(priorNode, currNode))
if ( foundTargetR ):
return (priorNodeR, foundTargetR, False)
else:
# if NOT FOUND, allow final processing
pass
# if we got here, we're exitting on a LEAF OR MID-LEVEL node,
# on NOT finding the Target on EITHER DEEPER LEFT or RIGHT sides,
# so return None!
return (priorNode, None, None)
# TODO: warnings on redefining prior, target, isTargetLChild from L213
# ATTN: init PRIOR to None and initialize currNode to root
def findTargetNode(self, targetNodeValue):
# ATTN: VALIDATION ERROR; to RAISE ERROR for EMPTY TREE!
if (self.root is None):
raise ValueError('Unable to find Target Node in Empty Tree!')
priorNode = None
currNode = self.root
isTargetLChild = None
priorNode, targetNode, isTargetLChild = self.findTargetNodeR( \
priorNode, currNode, targetNodeValue, None)
return (priorNode, targetNode, isTargetLChild)
def getLeftLeaf(self, currNode):
parent = None
leftLeaf = currNode
currNode = currNode.left
while (currNode):
parent = leftLeaf
leftLeaf = currNode
currNode = currNode.left
return (parent, leftLeaf)
# OUTLINE:
# - do the FIND for parent and target
# - do the CONNECT-SKIP from PARENT to the TARGET NEXT!
def delNode(self, targetNodeValue):
# ATTN: Python tuple trick for returning vals!
priorNode, targetNode, isTargetLChild = self.findTargetNode(targetNodeValue)
# CASE 0: not FOUND, and tree is not empty, return None
if self.root and (targetNode is None):
return None
# CASE 1: target is ROOT
if (priorNode is None) and targetNode:
self.root = None
# CASE 2: target is non-ROOT, and is a LEAF with NO children
elif targetNode and (targetNode.left is None) and (targetNode.right is None):
if priorNode and isTargetLChild:
priorNode.left = None
elif priorNode and not isTargetLChild:
priorNode.right = None
else:
print("UNHANDLED CASE 2; shouldn't happen")
# CASE 3a: target is non-ROOT, and has ONE child on RIGHT;
# is ITSELF RIGHT child
elif targetNode and (targetNode.left is None) and (targetNode.right):
if priorNode and isTargetLChild:
priorNode.left = targetNode.right
elif priorNode and not isTargetLChild:
priorNode.right = targetNode.right
else:
print("UNHANDLED CASE 3a; shouldn't happen")
# CASE 3b: target is non-ROOT, and has ONE child on LEFT;
# is ITSELF LEFT child
elif targetNode and (targetNode.left) and (targetNode.right is None):
if priorNode and isTargetLChild:
priorNode.left = targetNode.left
elif priorNode and not isTargetLChild:
priorNode.right = targetNode.left
else:
print("UNHANDLED CASE 3b; shouldn't happen")
# CASE 4: target is non-ROOT, and has TWO children
elif targetNode and targetNode.left and targetNode.right:
# PUNT: find any LEAF to replace Target Node to delete!
# - pick LEFT leaf off targetNode
parentNode, leftLeaf = self.getLeftLeaf(targetNode)
# detach leftLeaf within target's tree
parentNode.left = None
# attach target's Children to leftLeaf replacement
leftLeaf.left = targetNode.left
leftLeaf.right = targetNode.right
# now reattach leafLeaf replacing spot for targetNode
if priorNode and isTargetLChild:
priorNode.left = leftLeaf
elif priorNode and not isTargetLChild:
priorNode.right = leftLeaf
else:
print("UNHANDLED CASE 4; shouldn't happen")
else:
print("UNHANDLED CASE DETECTED!")
# ALWAYs return targetNode as deleted Node
return targetNode
# ************ TEST SCRIPT for FIND *********************
print("*********** TEST FIND *************")
# CASE 1a: ROOT is tree; matches Target to delete
print("\nCASE 1a")
binTree1 = BinTree(1)
(priorNode, targetNode, isTargetLChild) = binTree1.findTargetNode(1)
if targetNode:
print ("FOUND TARGET:")
print (targetNode.value)
if priorNode is None:
print ("TARGET NODE is ROOT of TREE")
# CASE 1b: ROOT is tree; but Target not found
print("\nCASE 1b")
binTree1 = BinTree(1)
(priorNode, targetNode, isTargetLChild) = binTree1.findTargetNode(-1)
if not targetNode:
print ("TARGET NOT FOUND IN TREE!")
if priorNode is None:
print ("TARGET NODE is not found in ROOT of TREE")
# CASE 2a: non-root, LEFT child; Target found
print("\nCASE 2a")
root2a = Node(3)
root2a.right = Node(2)
root2a.right.left = Node(1)
binTree2a = BinTree()
binTree2a.root = root2a
(priorNode, targetNode, isTargetLChild) = binTree2a.findTargetNode(2)
print ("TARGET NODE FOUND for 2a is: {} with value {}".format(targetNode, targetNode.value))
print ("PRIOR NODE FOUND for 2a is: {} with value {}".format(priorNode, priorNode.value))
# CASE 2b: non-root, RIGHT child; Target found
print("\nCASE 2b")
root2b = Node(3)
root2b.left = Node(2)
root2b.left.right = Node(1)
binTree2b = BinTree()
binTree2b.root = root2b
targetNode = binTree2b.findTargetNode(2)
(priorNode, targetNode, isTargetLChild) = binTree2b.findTargetNode(2)
print ("TARGET NODE FOUND for 2b is: {} with value {}".format(targetNode, targetNode.value))
print ("PRIOR NODE FOUND for 2b is: {} with value {}".format(priorNode, priorNode.value))
# CASE 3: non-root, TWO children; Target found
print("\nCASE 3")
root3 = Node(1)
root3.left = Node(2)
root3.right = Node(3)
root3.left.left = Node(4)
root3.left.right = Node(5)
root3.right.left = Node(6)
root3.right.right = Node(7)
root3.left.left.left = Node(8)
root3.left.left.right = Node(9)
root3.right.right.left = Node(10)
root3.right.right.right = Node(11)
binTree3 = BinTree()
binTree3.root = root3
(priorNode, targetNode, isTargetLChild) = binTree3.findTargetNode(2)
print ("\nTARGET NODE FOUND for 3a is: {} with value {}".format(targetNode, targetNode.value))
print ("PRIOR NODE FOUND for 3a is: {} with value {}".format(priorNode, priorNode.value))
(priorNode, targetNode, isTargetLChild) = binTree3.findTargetNode(3)
print ("\nTARGET NODE FOUND for 3b is: {} with value {}".format(targetNode, targetNode.value))
print ("PRIOR NODE FOUND for 3b is: {} with value {}".format(priorNode, priorNode.value))
(priorNode, targetNode, isTargetLChild) = binTree3.findTargetNode(4)
print ("\nTARGET NODE FOUND for 3c is: {} with value {}".format(targetNode, targetNode.value))
print ("PRIOR NODE FOUND for 3c is: {} with value {}".format(priorNode, priorNode.value))
(priorNode, targetNode, isTargetLChild) = binTree3.findTargetNode(7)
print ("\nTARGET NODE FOUND for 3d is: {} with value {}".format(targetNode, targetNode.value))
print ("PRIOR NODE FOUND for 3d is: {} with value {}".format(priorNode, priorNode.value))
# ************ TEST SCRIPT for DELETE *********************
print("\n********** TEST DELETE **********")
"""
# CASE 0: target IS ROOT, AND LEAF, and tree only has one node
print ("\nCASE 0: target IS ROOT, and tree has only one node")
binTree0 = BinTree(1)
removedNode = binTree0.delNode(1)
print("Removed Node with value: {}".format(removedNode.value))
print ("TREE CONTENTS: ")
print(binTree0)
print ("DONE.")
"""
"""
BINTREE 2b contents:
3
\
2
/
1
BINTREE3 contents:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \
8 9 10 11
"""
"""
# CASE 1: target HAS 0 children, IS A LEFT child LEAF
# TODO: CASE1 reuses binTree3 test data; so need to CLONE or COMMENT OUT
# BEFORE running this!
print ("\nCASE 1: target IS A LEAF, HAS NO CHILDREN, IS A LEFT child of parent")
print(binTree3)
removedNode = binTree3.delNode(8)
print("Removed Node with value: {}".format(removedNode.value))
print(binTree3)
"""
"""
# CASE 2: target has 1 child
print ("CASE 2b: target IS A RIGHT child; HAS A LEFT child")
print(binTree2a)
removedNode = binTree2a.delNode(2)
print("Removed Node with value: {}".format(removedNode.value))
print(binTree2a)
"""
"""
# CASE 3: target has 2 children
print ("CASE 3: target IS A RIGHT CHILD; HAS BOTH LEFT and RIGHT children")
print(binTree3)
removedNode = binTree3.delNode(7)
print("Removed Node with value: {}".format(removedNode.value))
print(binTree3)
"""
# CASE 4: target IS ANYTHING; but TREE is EMPTY
print ("\nCASE 4: target is ANYTHING; but TREE is EMPTY")
binTree4 = BinTree()
try:
removedNode = binTree4.delNode(1)
except ValueError as inputTreeErr:
print("CAUGHT INPUT ERROR")
print(inputTreeErr)
finally:
print(binTree4)
# CASE 5: target IS NOT in TREE; and have full tree
"""
# TODO: CASE1 reuses binTree3 test data; so need to CLONE or COMMENT OUT
# BEFORE running this!
print ("\nCASE 5: target IS NOT in TREE; and have full tree to search")
print(binTree3)
removedNode = binTree1.delNode(-1)
print("UNABLE TO FIND TARGET; returned removedNode {}".format(removedNode))
print(binTree3)
""""""
DELETE node from Binary Tree
CORE CASES:
*** CAREFUL/INTERESTING
-- need to distinguish applicable SIDE(left or right child); INTO TARGET from
PARENT, as well as OUT of TARGET
- target is root => reset root to None
- target has no child; and target is LEFT or RIGHT child of parent
=> reset parent's child (specific side) to None
- target has one child; and target is LEFT or RIGHT child of parent
=> reset parent child (specific side) to child of Target (specific side)
- target two children; and target is LEFT or RIGHT child of parent
=> find ANY LEAF off TARGET, for replacing itself
=> detach THAT leaf, append TARGET's 2 children to it
=> make this the child of the parent (specific side)
to replace TARGET
- empty tree => throw Exception as invalid input
KEY CONCEPTS:
1) FIND/TRAVERSAL, needs to know PARENT to TARGET node to delete WITHOUT Back Pointer, SO, need to traverse via DFS/Stack/Recursion vs BST/Loop
2) need to save TARGET's NEXT ptrs BEFORE deleting TARGET,
then attach PARENT pointers to TARGET'S NEXT
3) TRICKY -- need to distinguish applicable SIDE(left or right child); INTO TARGET from PARENT, as well as OUT of TARGET
4) visit ROOT FIRST to exit FASTEST if target no matched; and don't care about Left or Right since unordered BST => but ORDERED BST would be FASTER O(logN) avg or O(N) worst-case
5) BACKTRACK - LOCAL-REFERENCE-COPIES of RECURSIVE function args;
are POPPED from callstack on exit
6) EXIT THROUGH RECURSION LEVELS - on FOUND node, so return DEEPER results to (new)
vars that don't interfere with calling params
AT LEVEL
SIMPLIFY:
1) differentiate Tree from Node as need to distinguish ROOT vs generic NODE case
2) case for target having 2 children:
- EASIER - not sorted BST, as BIN TREE is UNORDERED!
- so just pick ANY leaf and swap it into the deleted target spot!
- vs for BST
- find IMMEDIATE PREDECESSOR LEAF (right child, then LEFT LEAF)
- move that entire RIGHT subtree to replace deleted node
- CAREFUL to SAVE remaining RIGHT subtree of deleted node;
as this will be attached to RIGHTMOST LEAF of above replacement subtree
3) breakup to code __REPR_, FIND wrapper with RECURSIVE helper; THEN DELNODE
"""
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
class BinTree:
def __init__(self, rootVal=None):
if rootVal:
self.root = Node(rootVal)
else:
self.root = None
# TODO: find out nice way to print tree structure!
def _recurPrint_(self, node, contents):
if node.left:
contents.append("/\n")
self._recurPrint_(node.left, contents)
if node:
contents.append('*{}*\n'.format(node.value))
if node.right:
contents.append("\\\n")
self._recurPrint_(node.right, contents)
return "".join(contents)
# TODO: best way to print output of tree!
# DEBUG: need to PRINT the TREE with MORE than LEVEL info; but BRANCHES
# so RECURSE vs BFS LOOP with sentinel break at each LEVEL!
# ===> SAY INORDER L, ROOT, RIGHT
def __repr__(self):
contents = []
strContents = ""
# ATTN: check for NONE, and also recurse on ROOT!
if self.root:
strContents = self._recurPrint_(self.root, contents)
else:
strContents = "EMPTY"
return strContents
# RECURSION NEEDED!
# DEBUG-TRICKY: we need to know from WHICH branch we got TO the targetNode
# to be able to connect correct branch of the priorNode to SKIP
# it! so use True for is Target LChild, None for ROOT,
# False for RChild
# TODO: could also find out how to do enumeration States!
def findTargetNodeR(self, priorNode, currNode, targetNodeValue, isTargetLChild):
# DEBUG: verifying DEEPER RECURSION CALL local node reference
# print ("ENTRY: prior{}, current{}".format(priorNode, currNode))
# EXIT immediately on FOUND; as no need to go DEEPER
if (currNode.value == targetNodeValue):
# ATTN: Python convenience can return TUPLE!
return (priorNode, currNode, None)
# RECURSE/ITERATE if children exist; down to LEAF Node
if (currNode.left):
priorNodeL, foundTargetL, isTargetLChild = self.findTargetNodeR( \
currNode, currNode.left, targetNodeValue, True)
# DEBUG: verifying DEEPER RECURSION CALL local node reference popped
# print ("RETURNL: prior{}, current{}".format(priorNode, currNode))
# ATTN: if FOUND, then accept (new) DEEP values to FORCE return
# BACK THROUGH MULTIPLE RECURSION LEVELs
# otherwise, ignore DEEP values;
# and retain LEVEL state to allow BACKTRACKING
if ( foundTargetL ):
return (priorNodeL, foundTargetL, True)
else:
# if NOT FOUND, allow further processing-recursion on RIGHT
pass
if (currNode.right):
priorNodeR, foundTargetR, isTargetLChild = self.findTargetNodeR( \
currNode, currNode.right, targetNodeValue, False)
# ATTN: verifying DEEPER RECURSION CALL local node reference popped
# print ("RETURNR: prior{}, current{}".format(priorNode, currNode))
if ( foundTargetR ):
return (priorNodeR, foundTargetR, False)
else:
# if NOT FOUND, allow final processing
pass
# if we got here, we're exitting on a LEAF OR MID-LEVEL node,
# on NOT finding the Target on EITHER DEEPER LEFT or RIGHT sides,
# so return None!
return (priorNode, None, None)
# TODO: warnings on redefining prior, target, isTargetLChild from L213
# ATTN: init PRIOR to None and initialize currNode to root
def findTargetNode(self, targetNodeValue):
# ATTN: VALIDATION ERROR; to RAISE ERROR for EMPTY TREE!
if (self.root is None):
raise ValueError('Unable to find Target Node in Empty Tree!')
priorNode = None
currNode = self.root
isTargetLChild = None
priorNode, targetNode, isTargetLChild = self.findTargetNodeR( \
priorNode, currNode, targetNodeValue, None)
return (priorNode, targetNode, isTargetLChild)
def getLeftLeaf(self, currNode):
parent = None
leftLeaf = currNode
currNode = currNode.left
while (currNode):
parent = leftLeaf
leftLeaf = currNode
currNode = currNode.left
return (parent, leftLeaf)
# OUTLINE:
# - do the FIND for parent and target
# - do the CONNECT-SKIP from PARENT to the TARGET NEXT!
def delNode(self, targetNodeValue):
# ATTN: Python tuple trick for returning vals!
priorNode, targetNode, isTargetLChild = self.findTargetNode(targetNodeValue)
# CASE 0: not FOUND, and tree is not empty, return None
if self.root and (targetNode is None):
return None
# CASE 1: target is ROOT
if (priorNode is None) and targetNode:
self.root = None
# CASE 2: target is non-ROOT, and is a LEAF with NO children
elif targetNode and (targetNode.left is None) and (targetNode.right is None):
if priorNode and isTargetLChild:
priorNode.left = None
elif priorNode and not isTargetLChild:
priorNode.right = None
else:
print("UNHANDLED CASE 2; shouldn't happen")
# CASE 3a: target is non-ROOT, and has ONE child on RIGHT;
# is ITSELF RIGHT child
elif targetNode and (targetNode.left is None) and (targetNode.right):
if priorNode and isTargetLChild:
priorNode.left = targetNode.right
elif priorNode and not isTargetLChild:
priorNode.right = targetNode.right
else:
print("UNHANDLED CASE 3a; shouldn't happen")
# CASE 3b: target is non-ROOT, and has ONE child on LEFT;
# is ITSELF LEFT child
elif targetNode and (targetNode.left) and (targetNode.right is None):
if priorNode and isTargetLChild:
priorNode.left = targetNode.left
elif priorNode and not isTargetLChild:
priorNode.right = targetNode.left
else:
print("UNHANDLED CASE 3b; shouldn't happen")
# CASE 4: target is non-ROOT, and has TWO children
elif targetNode and targetNode.left and targetNode.right:
# PUNT: find any LEAF to replace Target Node to delete!
# - pick LEFT leaf off targetNode
parentNode, leftLeaf = self.getLeftLeaf(targetNode)
# detach leftLeaf within target's tree
parentNode.left = None
# attach target's Children to leftLeaf replacement
leftLeaf.left = targetNode.left
leftLeaf.right = targetNode.right
# now reattach leafLeaf replacing spot for targetNode
if priorNode and isTargetLChild:
priorNode.left = leftLeaf
elif priorNode and not isTargetLChild:
priorNode.right = leftLeaf
else:
print("UNHANDLED CASE 4; shouldn't happen")
else:
print("UNHANDLED CASE DETECTED!")
# ALWAYs return targetNode as deleted Node
return targetNode
# ************ TEST SCRIPT for FIND *********************
print("*********** TEST FIND *************")
# CASE 1a: ROOT is tree; matches Target to delete
print("\nCASE 1a")
binTree1 = BinTree(1)
(priorNode, targetNode, isTargetLChild) = binTree1.findTargetNode(1)
if targetNode:
print ("FOUND TARGET:")
print (targetNode.value)
if priorNode is None:
print ("TARGET NODE is ROOT of TREE")
# CASE 1b: ROOT is tree; but Target not found
print("\nCASE 1b")
binTree1 = BinTree(1)
(priorNode, targetNode, isTargetLChild) = binTree1.findTargetNode(-1)
if not targetNode:
print ("TARGET NOT FOUND IN TREE!")
if priorNode is None:
print ("TARGET NODE is not found in ROOT of TREE")
# CASE 2a: non-root, LEFT child; Target found
print("\nCASE 2a")
root2a = Node(3)
root2a.right = Node(2)
root2a.right.left = Node(1)
binTree2a = BinTree()
binTree2a.root = root2a
(priorNode, targetNode, isTargetLChild) = binTree2a.findTargetNode(2)
print ("TARGET NODE FOUND for 2a is: {} with value {}".format(targetNode, targetNode.value))
print ("PRIOR NODE FOUND for 2a is: {} with value {}".format(priorNode, priorNode.value))
# CASE 2b: non-root, RIGHT child; Target found
print("\nCASE 2b")
root2b = Node(3)
root2b.left = Node(2)
root2b.left.right = Node(1)
binTree2b = BinTree()
binTree2b.root = root2b
targetNode = binTree2b.findTargetNode(2)
(priorNode, targetNode, isTargetLChild) = binTree2b.findTargetNode(2)
print ("TARGET NODE FOUND for 2b is: {} with value {}".format(targetNode, targetNode.value))
print ("PRIOR NODE FOUND for 2b is: {} with value {}".format(priorNode, priorNode.value))
# CASE 3: non-root, TWO children; Target found
print("\nCASE 3")
root3 = Node(1)
root3.left = Node(2)
root3.right = Node(3)
root3.left.left = Node(4)
root3.left.right = Node(5)
root3.right.left = Node(6)
root3.right.right = Node(7)
root3.left.left.left = Node(8)
root3.left.left.right = Node(9)
root3.right.right.left = Node(10)
root3.right.right.right = Node(11)
binTree3 = BinTree()
binTree3.root = root3
(priorNode, targetNode, isTargetLChild) = binTree3.findTargetNode(2)
print ("\nTARGET NODE FOUND for 3a is: {} with value {}".format(targetNode, targetNode.value))
print ("PRIOR NODE FOUND for 3a is: {} with value {}".format(priorNode, priorNode.value))
(priorNode, targetNode, isTargetLChild) = binTree3.findTargetNode(3)
print ("\nTARGET NODE FOUND for 3b is: {} with value {}".format(targetNode, targetNode.value))
print ("PRIOR NODE FOUND for 3b is: {} with value {}".format(priorNode, priorNode.value))
(priorNode, targetNode, isTargetLChild) = binTree3.findTargetNode(4)
print ("\nTARGET NODE FOUND for 3c is: {} with value {}".format(targetNode, targetNode.value))
print ("PRIOR NODE FOUND for 3c is: {} with value {}".format(priorNode, priorNode.value))
(priorNode, targetNode, isTargetLChild) = binTree3.findTargetNode(7)
print ("\nTARGET NODE FOUND for 3d is: {} with value {}".format(targetNode, targetNode.value))
print ("PRIOR NODE FOUND for 3d is: {} with value {}".format(priorNode, priorNode.value))
# ************ TEST SCRIPT for DELETE *********************
print("\n********** TEST DELETE **********")
"""
# CASE 0: target IS ROOT, AND LEAF, and tree only has one node
print ("\nCASE 0: target IS ROOT, and tree has only one node")
binTree0 = BinTree(1)
removedNode = binTree0.delNode(1)
print("Removed Node with value: {}".format(removedNode.value))
print ("TREE CONTENTS: ")
print(binTree0)
print ("DONE.")
"""
"""
BINTREE 2b contents:
3
\
2
/
1
BINTREE3 contents:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \
8 9 10 11
"""
"""
# CASE 1: target HAS 0 children, IS A LEFT child LEAF
# TODO: CASE1 reuses binTree3 test data; so need to CLONE or COMMENT OUT
# BEFORE running this!
print ("\nCASE 1: target IS A LEAF, HAS NO CHILDREN, IS A LEFT child of parent")
print(binTree3)
removedNode = binTree3.delNode(8)
print("Removed Node with value: {}".format(removedNode.value))
print(binTree3)
"""
"""
# CASE 2: target has 1 child
print ("CASE 2b: target IS A RIGHT child; HAS A LEFT child")
print(binTree2a)
removedNode = binTree2a.delNode(2)
print("Removed Node with value: {}".format(removedNode.value))
print(binTree2a)
"""
"""
# CASE 3: target has 2 children
print ("CASE 3: target IS A RIGHT CHILD; HAS BOTH LEFT and RIGHT children")
print(binTree3)
removedNode = binTree3.delNode(7)
print("Removed Node with value: {}".format(removedNode.value))
print(binTree3)
"""
# CASE 4: target IS ANYTHING; but TREE is EMPTY
print ("\nCASE 4: target is ANYTHING; but TREE is EMPTY")
binTree4 = BinTree()
try:
removedNode = binTree4.delNode(1)
except ValueError as inputTreeErr:
print("CAUGHT INPUT ERROR")
print(inputTreeErr)
finally:
print(binTree4)
# CASE 5: target IS NOT in TREE; and have full tree
"""
# TODO: CASE1 reuses binTree3 test data; so need to CLONE or COMMENT OUT
# BEFORE running this!
print ("\nCASE 5: target IS NOT in TREE; and have full tree to search")
print(binTree3)
removedNode = binTree1.delNode(-1)
print("UNABLE TO FIND TARGET; returned removedNode {}".format(removedNode))
print(binTree3)
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment