Skip to content

Instantly share code, notes, and snippets.

@econchick
Created January 29, 2013 18:24
Show Gist options
  • Select an option

  • Save econchick/4666378 to your computer and use it in GitHub Desktop.

Select an option

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
Copy Markdown

kabhish commented Oct 15, 2017

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

@amityadav9314
Copy link
Copy Markdown

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