Create the code in class on Binary Tree (BT) to enable user to • insert some nod

Question

Create the code in class on Binary Tree (BT) to enable user to • insert some nodes (Root/Right/Left Child), • getSize of the tree(), • height and depth of a given node(), • IsInternal node(), • IsExternal node() • CoutrightChild of any given node(), • CountleftChild of any given node(), • num children of a given node () • delete node() • Find a given target node from the list of nodes(). Create the code in class on Binary Tree (BT) to enable user to • insert some nodes (Root/Right/Left Child), • getSize of the tree(), • height and depth of a given node(), • IsInternal node(), • IsExternal node() • CoutrightChild of any given node(), • CountleftChild of any given node(), • num children of a given node () • delete node() • Find a given target node from the list of nodes().
*The example code as in the attached picture.
"""node class is superclass, BSTree is subclass" class Node (object): def -init-(self,info): self.info = info self.left None self.rightNone class BSTree (object): EXAMPLE ONLY def init (self): self.root None def create(self,value): if self.root == None : sel f . root Node ( value ) else: currentself.root while 1: if value current.info: current current.right else: current.right # Node (value) break def inorder (self,node): if node is not None: self.inorder (node.left) print (node.info) self.inorder (node.right) myTree BSTree () array [0,3,1,6,4,7,10,14,13] for i in array: myTree.create(i) print( "data =", array) print("in order transversal") myTree.inorder (myTree.root)

Explanation / Answer

# A utility function to insert a new node with the given key

def insert(root,node):

    if root is None:

        root = node

    else:

        if root.val < node.val:

            if root.right is None:

                root.right = node

            else:

                insert(root.right, node)

        else:

            if root.left is None:

                root.left = node

            else:

                insert(root.left, node)

#getSize of the tree()

def size(self):

if self.left is None or self.right is None:

leftSize = self.left.size() if self.left else 0

rightSize = self.right.size() if self.right else 0

return leftSize + 1 + rightSize

else:

return self.left.size()+1+self.right.size()

#height and depth of a given node(),

def maxDepth(node):
if node is None:
return 0 ;

else :

# Compute the depth of each subtree
lDepth = maxDepth(node.left)
rDepth = maxDepth(node.right)

# Use the larger one
if (lDepth > rDepth):
return lDepth+1
else:
return rDepth+1

# Function to get the left count nodes
def CountleftChild(node):
if node is None:
return 0
if(node.left is None):
return 1
else:
return CountleftChild(node.left)

# Function to get the right count nodes

def CoutrightChild(node):
if node is None:
return 0
if(node.left is None):
return 1
else:
return CoutrightChild(node.right)

#delete node()

if root is None:
return root

# If the key to be deleted is similiar than the root's
# key then it lies in left subtree
if key < root.key:
root.left = deleteNode(root.left, key)

# If the kye to be delete is greater than the root's key
# then it lies in right subtree
elif(key > root.key):
root.right = deleteNode(root.right, key)

# If key is same as root's key, then this is the node
# to be deleted
else:

# Node with only one child or no child
if root.left is None :
temp = root.right
root = None
return temp

elif root.right is None :
temp = root.left
root = None
return temp

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.