Scribd
Upload
158 views

Binary Tree (Python) - All Codes

This document defines classes and methods for binary trees in Python. It includes a BinaryTree class with methods for inserting nodes, traversing the tree, finding the number of nodes, height, leaf nodes, and checking if the tree is balanced. A BinaryNode class is also defined to represent individual nodes with left and right child pointers. Methods are provided to create a tree from inorder and preorder traversals, remove leaf nodes, and perform other tree operations and traversals.

Uploaded by

Pragya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as RTF, PDF, TXT or read online on Scribd
158 views

Binary Tree (Python) - All Codes

This document defines classes and methods for binary trees in Python. It includes a BinaryTree class with methods for inserting nodes, traversing the tree, finding the number of nodes, height, leaf nodes, and checking if the tree is balanced. A BinaryNode class is also defined to represent individual nodes with left and right child pointers. Methods are provided to create a tree from inorder and preorder traversals, remove leaf nodes, and perform other tree operations and traversals.

Uploaded by

Pragya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as RTF, PDF, TXT or read online on Scribd
You are on page 1/ 4

# Online Python compiler (interpreter) to run Python online.

# Write Python 3 code in this online editor and run it.


class BNT:
def __init__(self, data):
self.data = data
self.left = None
self.right = None

class BinaryTree:
root = None
que = []

def insert(self, data):


if self.root == None:
self.root = BNT(data)
return

q = []
q.append(self.root)

while len(q) > 0:


temp = q.pop(0)

if temp.left == None:
temp.left = BNT(data)
break
else:
q.append(temp.left)

if temp.right == None:
temp.right = BNT(data)
break
else:
q.append(temp.right)

def insertLevelWise(self, arr):


q = []
q.append(BNT(arr.pop(0)))

while len(q) > 0:


temp = q.pop(0)

if self.root == None:
self.root = temp

left_val = arr.pop(0)
right_val = arr.pop(0)

if left_val != -1:
left = BNT(left_val)
q.append(left)
temp.left = left

if right_val != -1:
right = BNT(right_val)
q.append(right)
temp.right = right

def CreateTreeInAndPre(preorder, inorder):


root = BNT(preorder.pop(0))
idx = inorder.index(root.data)

left = BinaryTree()
right = BinaryTree()

for i in range (0, idx):


left.insert(preorder.pop(0))

for i in range (idx+1, len(inorder)):


right.insert(preorder.pop(0))

root.left = left.root
root.right = right.root
return root

def traverse(root):
if root == None:
return
print(root.data, sep = " ")
traverse(root.left)
traverse(root.right)

def traverseQue(root, que):


if (root == None):
return

print(root.data)
if (root.left != None):
que.append(root.left)
if (root.right != None):
que.append(root.right)
que.pop(0)
if (len(que) > 0):
traverseQue(que[0], que)

def numNodes(root):
if root == None:
return 0
left = numNodes(root.left)
right = numNodes(root.right)
return 1 + left + right

def findMax(root):
if root == None:
return 0
left = findMax(root.left)
right = findMax(root.right)

return max(left, right, root.data)

def findHeight(root):
if root == None:
return 0

return 1 + max(findHeight(root.left), findHeight(root.right))

def numLeafNodes(root):
if (root == None):
return 0
if (root.left == None and root.right == None):
return 1

return numLeafNodes(root.left) + numLeafNodes(root.right)

def atDep(root, k):


if root == None:
return
if k == 0:
print(root.data)
return

atDep(root.left, k-1)
atDep(root.right, k-1)

def removeLeaf(root):

if root == None:
return

if root.left == None and root.right == None:


return True

if (removeLeaf(root.left)):
root.left = None

if (removeLeaf(root.right)):
root.right = None
def checkBalanced(root):
if root == None:
return False
if (root.left == None and root.right != None) or (root.left != None and root.right ==
None):
return False
if root.left == None and root.right == None:
return True

return checkBalanced(root.left) and checkBalanced(root.right)

b = BinaryTree()
# l = [1,2,3,4,5,-1,-1,8,-1,-1,-1,-1,-1]
# b.insertLevelWise(l)
# que = [b.root]
# traverseQue(b.root, que)
inorder = [4,2,5,1,6,3,7]
preorder = [1,2,4,5,3,6,7]
root = CreateTreeInAndPre(preorder, inorder)
traverse(root)

You might also like