Scribd
Upload
70 views4 pages

Python Binary Tree Implementation

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
70 views4 pages

Python Binary Tree Implementation

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

# 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):
[Link] = data
[Link] = None
[Link] = None

class BinaryTree:
root = None
que = []

def insert(self, data):


if [Link] == None:
[Link] = BNT(data)
return

q = []
[Link]([Link])

while len(q) > 0:


temp = [Link](0)

if [Link] == None:
[Link] = BNT(data)
break
else:
[Link]([Link])

if [Link] == None:
[Link] = BNT(data)
break
else:
[Link]([Link])

def insertLevelWise(self, arr):


q = []
[Link](BNT([Link](0)))

while len(q) > 0:


temp = [Link](0)

if [Link] == None:
[Link] = temp

left_val = [Link](0)
right_val = [Link](0)

if left_val != -1:
left = BNT(left_val)
[Link](left)
[Link] = left

if right_val != -1:
right = BNT(right_val)
[Link](right)
[Link] = right

def CreateTreeInAndPre(preorder, inorder):


root = BNT([Link](0))
idx = [Link]([Link])

left = BinaryTree()
right = BinaryTree()

for i in range (0, idx):


[Link]([Link](0))

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


[Link]([Link](0))

[Link] = [Link]
[Link] = [Link]
return root

def traverse(root):
if root == None:
return
print([Link], sep = " ")
traverse([Link])
traverse([Link])

def traverseQue(root, que):


if (root == None):
return

print([Link])
if ([Link] != None):
[Link]([Link])
if ([Link] != None):
[Link]([Link])
[Link](0)
if (len(que) > 0):
traverseQue(que[0], que)

def numNodes(root):
if root == None:
return 0
left = numNodes([Link])
right = numNodes([Link])
return 1 + left + right

def findMax(root):
if root == None:
return 0
left = findMax([Link])
right = findMax([Link])

return max(left, right, [Link])

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

return 1 + max(findHeight([Link]), findHeight([Link]))

def numLeafNodes(root):
if (root == None):
return 0
if ([Link] == None and [Link] == None):
return 1

return numLeafNodes([Link]) + numLeafNodes([Link])

def atDep(root, k):


if root == None:
return
if k == 0:
print([Link])
return

atDep([Link], k-1)
atDep([Link], k-1)

def removeLeaf(root):

if root == None:
return

if [Link] == None and [Link] == None:


return True

if (removeLeaf([Link])):
[Link] = None

if (removeLeaf([Link])):
[Link] = None
def checkBalanced(root):
if root == None:
return False
if ([Link] == None and [Link] != None) or ([Link] != None and [Link] ==
None):
return False
if [Link] == None and [Link] == None:
return True

return checkBalanced([Link]) and checkBalanced([Link])

b = BinaryTree()
# l = [1,2,3,4,5,-1,-1,8,-1,-1,-1,-1,-1]
# [Link](l)
# que = [[Link]]
# traverseQue([Link], 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