iterative preorder, inorder, postorder tree traversals

took some time to browse through the geeksforgeeks for postorder and inorder!

	#!/usr/bin/env python
	# -*- encoding: UTF-8 -*-
	from __future__ import print_function
	from collections import deque
	class bistnode:
	def __init__(self, data=0, parent=None):
	self.parent = parent
	self.data = data
	self.left = None
	self.right = None
	def nukethem(self):
	self.parent = None
	self.left = None
	self.right = None
	def __repr__(self):
	return "[data={}, left={}, right={}]".format(
	self.data,
	self.left,
	self.right)
	class bist:
	def __init__(self):
	self.root = None
	def insert(self, data):
	if self.root is None:
	self.root = bistnode(data)
	return
	node = self.root
	while True:
	if node.data >= data:
	if node.left is None:
	node.left = bistnode(data)
	node.left.parent = node
	return
	node = node.left
	else:
	if node.right is None:
	node.right = bistnode(data)
	node.right.parent = node
	return
	node = node.right
	def leftmost(self, node=None):
	node = node or self.root
	while node.left is not None:
	node = node.left
	return node
	def rightmost(self, node=None):
	node = node or self.root
	while node.right is not None:
	node = node.right
	return node
	def dft(self, process):
	stack = deque([self.root])
	while stack:
	node = stack.pop()
	if process(node):
	return
	if node.right is not None:
	stack.append(node.right)
	if node.left is not None:
	stack.append(node.left)
	def bft(self, process):
	queue = deque([self.root])
	while queue:
	node = queue.pop()
	if process(node):
	return
	if node.left is not None:
	queue.appendleft(node.left)
	if node.right is not None:
	queue.appendleft(node.right)
	def postorder(self):
	stack = []
	current = self.root
	while True:
	while current is not None:
	stack.append(current.right)
	stack.append(current)
	current = current.left
	current = stack.pop()
	if current and stack and current.right is stack[-1]:
	stack.pop()
	stack.append(current)
	current = current.right
	elif current:
	print(current.data)
	current = None
	if not stack:
	break
	def inorder(self):
	stack = []
	current = self.root
	while True:
	while current is not None:
	stack.append(current.right)
	stack.append(current)
	current = current.left
	current = stack.pop()
	if current:
	print(current.data)
	current = stack.pop()
	if not (stack or current):
	break
	def preorder(self):
	self.dft(lambda x: print(x.data))
	def bist_tests():
	binary_search_tree = bist()
	import random
	k = []
	for x in xrange(10):
	k.append(random.randint(0, 100))
	binary_search_tree.insert(k[-1])
	print(k)
	print(binary_search_tree.root)
	print()
	binary_search_tree.preorder()
	print()
	binary_search_tree.inorder()
	print()
	binary_search_tree.postorder()
	if __name__ == '__main__':
	bist_tests()

view raw bist.py hosted with ❤ by GitHub