Skip to content

Instantly share code, notes, and snippets.

@econchick
Created January 29, 2013 18:24
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save econchick/4666378 to your computer and use it in GitHub Desktop.
Save econchick/4666378 to your computer and use it in GitHub Desktop.
Implement a Binary Tree in Python
class Node:
def __init__(self, key):
self.key = key
self.parent = None
self.left = None
self.right = None
def insert(root, t):
new = Node(t)
if root == None:
root = new
else:
node = root
while True:
if t < node.key:
# go left
if node.left == None:
node.left = new
node.parent = node
break
node = node.left
else:
# go right
if node.right is None:
node.right = new
node.parent = node
break
node = node.right
return new
def find(root, t):
node = root
if t == node.key:
return node
while node is not None:
if t == node.key
return node
elif t < node.key:
node = node.left
else:
node = node.right
return node
def get_height(root):
if root == None:
return 0
return max(get_height(root.left), get_height(root.right)) + 1
def is_balanced(root):
if root == None:
return True
height_diff = get_height(root.left) - get_height(root.right)
if abs(height_diff) > 1:
return False
else:
return is_balanced(root.left) and is_balanced(root.right)
self.root = root
@kabhish
Copy link

kabhish commented Oct 15, 2017

On line 20, node.parent = node is wrong.
It should be new.parent = node;

@amityadav9314
Copy link

This is BST, what about Binary Tree implementations?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment