Trees - mani2885/puzzles GitHub Wiki

Binary Search Trees

A BST is a binary tree where nodes are ordered in the following way:

  1. each node contains one key (also known as data)
  2. the keys in the left subtree are less then the key in its parent node, in short L < P;
  3. the keys in the right subtree are greater the key in its parent node, in short P < R;
  4. duplicate keys are not allowed.

Class for Tree Node:

class Node:
	def __init__(self,value,parent=None,leftchild=None,rightchild=None):
		self.value = value
		self.parent = parent
		self.leftchild = leftchild
		self.rightchild = rightchild

	def hasleftchild(self):
		return (self.leftchild != None)

	def hasrightchild(self):
		return (self.rightchild != None)

Class for Binary Search Tree (BST)

class BST:
	def __init__(self):
		self.root = None
		self.size = 0

	def _add(self,currnode,value):
		if value < currnode.value:
			if currnode.hasleftchild():
				self._add(currnode.leftchild,value)
			else:
				currnode.leftchild = Node(value)
				self.size = self.size + 1
		else:
			if currnode.hasrightchild():
				self._add(currnode.rightchild,value)
			else:
				currnode.rightchild = Node(value)
				self.size = self.size + 1

	def add(self, value):
		if self.root == None:
			self.root = Node(value)
			self.size = self.size + 1
		else:
			self._add(self.root,value)

Adding a node to BST

			
if __name__ == "__main__":
	b = BST()
	#http://btechsmartclass.com/DS/images/BST%20Example.png
	nums = [25, 20, 36, 10, 22, 30, 40, 5, 12, 28, 38, 48, 1, 8, 15, 45, 50]
	for k in nums:
		b.add(k)

The BST tree after the above operation will be:

Given a tree, is it a BST?

Before we attempt to answer this question, let us first look at what property distinguishes a BST from a non-BST. Take any subtree in the BST and we find that the root node is >= left node and root node is < right node. We can use this property to check if a tree is BST or not:

	def _isBST(self, node):
		if node is None:
			return True
		if node.hasleftchild():
			if node.value < node.leftchild.value:
				return False
		if node.hasrightchild():
			if node.value > node.rightchild.value:
				return False
		return self._isBST(node.leftchild) and self._isBST(node.rightchild)
	
	def isBST(self):
		return self._isBST(self.root)

There is another property of BST that we can take advantage. If we perform an InOrder traversal on a BST, we end up visiting the nodes in the increasing order of the keys.

There are in fact three different types of depth-first traversals on trees:

  • PreOrder traversal - visit the parent first and then left and right children;
  • InOrder traversal - visit the left child, then the parent and the right child;
  • PostOrder traversal - visit left child, then the right child and then the parent;

The picture below demonstrates the order of node visitation. Number 1 denote the first node in a particular traversal and 7 denote the last node. Source: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html

These common traversals can be represented as a single algorithm by assuming that we visit each node three times. An Euler tour is a walk around the binary tree where each edge is treated as a wall, which you cannot cross. In this walk each node will be visited either on the left, or under the below, or on the right. The Euler tour in which we visit nodes on the left produces a preorder traversal. When we visit nodes from the below, we get an inorder traversal. And when we visit nodes on the right, we get a postorder traversal. Source: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html Source: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html

Applying InOrder traversal to our example, we see that the nodes are visited in the increasing order of key value. The corresponding code is:

def _inOrder(self,node):
	if (node is None):
		return
	else:
		self._inOrder(node.leftchild) 
		print(node.value, end=' ')
		self._inOrder(node.rightchild)

def inOrder(self):
	self._inOrder(self.root)

Output is:

1 5 8 10 12 15 20 22 25 28 30 36 38 40 45 48 50

The code for preOrder and postOrder traversal are:

def _preOrder(self,node):
	if (node is None):
		return
	else:
		print(node.value, end=' ')
		self._preOrder(node.leftchild) 
		self._preOrder(node.rightchild)

def preOrder(self):
	self._preOrder(self.root)

Output is:

25 20 10 5 1 8 12 15 22 36 30 28 40 38 48 45 50

def _postOrder(self,node):
	if (node is None):
		return
	else:
		self._postOrder(node.leftchild) 
		self._postOrder(node.rightchild)
		print(node.value, end=' ')

def postOrder(self):
	self._postOrder(self.root)

Output is:

1 8 5 15 12 10 22 20 28 30 38 45 50 48 40 36 25

Now back to our original problem - if an inOrder traversal does not follow an increasing order of the keys, then the tree is not a BST. The main idea is to do an inOrder traversal and at every step check if the key value of current node is greater than that of the previous node. Note the placement of the print statement in the code for inOrder traversal. This is where we arrive at each node during the traversal and this is where we have to check the condition for BST. In the code below, a recursive call to self._isBST2(node.leftchild,prevnode) will lead to the first visitor node, the node with minimum key value in the BST (leftmost node), and until then prevnode is None as we are yet to visit the first node. The same argument holds for any subtree. After we have reached the min node of the subtree, we assign node to prevnode and resume the recursive calls. Note that self._isBST2(node.rightchild,node) is a return argument since a Boolean output is expected.

def _isBST2(self,node,prevnode=None):
	# parent was last node in the traversal path
	if node is None:
		return True
	else:
		self._isBST2(node.leftchild,prevnode)
		if prevnode is not None and prevnode.value > node.value:
			return False
	return self._isBST2(node.rightchild,node)

def isBST2(self):
	return self._isBST2(self.root)

There is one more operation on BST that takes advantage of inOrder traversal property. How do we delete a node in the BST and still not break the property of BST? The node to delete may have:

  1. no children
  2. one children
  3. both children

For removing a leaf node, find the previous node and detach + delete the leaf node.

	def _findprev(self, node, value):
		if node is None:
			return None

		if (node.hasleftchild() and node.leftchild.value == value) or \
			(node.hasrightchild() and node.rightchild.value == value):
			return node
		elif value > node.value:
			return self._findprev(node.rightchild, value)
		elif value < node.value:
			return self._findprev(node.leftchild, value)
	
	def findprev(self, value):
		return self._findprev(self.root, value)
	
	def remove(self, value):
		# node to remove is leaf node
		parent = self.findprev(value)
		if parent is not None:
			if parent.hasleftchild() and parent.leftchild.value == value:
				del parent.leftchild
				parent.leftchild = None
			elif parent.hasrightchild() and parent.rightchild.value == value:
				del parent.rightchild
				parent.rightchild = None

Binary Trees

Let us now consider a Binary Tree (BT). A BT need not satisfy the last 3 conditions of a BST:

  1. each node contains one key (also known as data)
  2. the keys in the left subtree are less then the key in its parent node, in short L < P;
  3. the keys in the right subtree are greater the key in its parent node, in short P < R;
  4. duplicate keys are not allowed.

Since there is no constraint on where to place a new node in a BT, how to we select the position for the new node? One way is to visits nodes by levels from top to bottom and from left to right and insert the new node in the first empty location. This type of traversal is called the "level order" traversal and is the only kind of "breadth-first" traversal.

If we were to perform a levelOrder traversal on our BST example, the output will be: 25 20 36 10 22 30 40 5 12 28 38 48 1 8 15 45 50 The logic for this traversal method would be:

  • Initialize a FIFO queue and add the root node to queue.

  • Until all nodes are traversed −

  1. dequeue the node at the head of the queue

  2. enqueue or append its left child and right child (in that order) to end of the queue

  3. repeat steps 1 and 2

from collections import deque

def levelOrder(self):
	queue = deque()
	queue.append(self.root)
	self._levelOrder(queue)
	
def _levelOrder(self,queue):
	if not queue:
		return
	head = queue.popleft()
	print(head.value, end=' ')
	[ queue.append(node) for node in [head.leftchild, head.rightchild] if node]
	if queue:
		self._levelOrder(queue)

Lets apply levelOrder traversal for the BST example. Output is:

25 20 36 10 22 30 40 5 12 28 38 48 1 8 15 45 50

Below is the code for adding node in levelOrder. Assign the new key value to the first empty child we encounter during the traversal (note we first visit the left child first and then the right child):

class BT:
	def __init__(self):
		self.root = None
		self.size = 0
	
	def _add(self,queue,value):
		if not queue:
			return
		head = queue.popleft()
		for node in [head.leftchild, head.rightchild]:
			if node:
				queue.append(node)
			elif not head.hasleftchild():
				head.leftchild = Node(value)
				return
			elif not head.hasrightchild():
				head.rightchild = Node(value)
				return
		if queue:
			self._add(queue, value)
			
	def add(self, value):
		if self.root == None:
			self.root = Node(value)
			self.size = self.size + 1
		else:
			q = deque()
			q.append(self.root)
			self._add(q,value)