classBSTNode:def__init__(self,value): self.value = value self.left =None self.right =Nonedefinsert(self,value):# create a node for the new value new_node =BSTNode(value)# compare the node value to the self valueif ( new_node.value <= self.value ):# less then or equal to will all go to the left if any duplicats too# we add to the leftif self.left isNone: self.left = new_nodeelse: self.left.insert(value)else:# we add to the right# if space existsif self.right isNone: self.right = new_nodeelse: self.right.insert(value)defsearch(self,target):if target == self.value:returnTrue# check if value is less than self.valueif target < self.value:# look to the leftif self.left isNone:returnFalsereturn self.left.search(target)else:# look to the rightif self.right isNone:returnFalsereturn self.right.search(target)deffind_minimum_value(self):# if self.left is None: #recursive here# return self.value# min_value = self.left.find_minimum_value()# return min_value curr_node = selfwhile curr_node.left isnotNone: curr_node = curr_node.leftreturn curr_node.valueroot =BSTNode(10)# root.left = BSTNode(6)# root.right = BSTNode(12)root.insert(6)root.insert(7)root.insert(12)root.insert(5)root.insert(14)root.insert(8)print(f"minimum value in tree is: {root.find_minimum_value()}")print(f"does 8 exist? {root.search(8)}")print(f"does 8 exist? {root.search(7)}")print(f"does 8 exist? {root.search(15)}")
classBSTNode:def__init__(self,value): self.value = value self.left =None self.right =Nonedefinsert(self,value):# create a node for the new value new_node =BSTNode(value)# compare the node value to the self valueif ( new_node.value <= self.value ):# less then or equal to will all go to the left if any duplicats too# we add to the leftif self.left isNone: self.left = new_nodeelse: self.left.insert(value)else:# we add to the right# if space existsif self.right isNone: self.right = new_nodeelse: self.right.insert(value)defsearch(self,target):if target == self.value:returnTrue# check if value is less than self.valueif target < self.value:# look to the leftif self.left isNone:returnFalsereturn self.left.search(target)else:# look to the rightif self.right isNone:returnFalsereturn self.right.search(target)deffind_minimum_value(self):# if self.left is None: #recursive here# return self.value# min_value = self.left.find_minimum_value()# return min_value curr_node = selfwhile curr_node.left isnotNone: curr_node = curr_node.leftreturn curr_node.valueroot =BSTNode(10)# root.left = BSTNode(6)# root.right = BSTNode(12)root.insert(6)root.insert(7)root.insert(12)root.insert(5)root.insert(14)root.insert(8)print(f"minimum value in tree is: {root.find_minimum_value()}")print(f"does 8 exist? {root.search(8)}")print(f"does 8 exist? {root.search(7)}")print(f"does 8 exist? {root.search(15)}")classBSTNode:def__init__(self,value): self.value = value self.left =None self.right =Nonedefinsert(self,value):# create a node for the new value new_node =BSTNode(value)# compare the node value to the self valueif ( new_node.value <= self.value ):# less then or equal to will all go to the left if any duplicats too# we add to the leftif self.left isNone: self.left = new_nodeelse: self.left.insert(value)else:# we add to the right# if space existsif self.right isNone: self.right = new_nodeelse: self.right.insert(value)defsearch(self,target):if target == self.value:returnTrue# check if value is less than self.valueif target < self.value:# look to the leftif self.left isNone:returnFalsereturn self.left.search(target)else:# look to the rightif self.right isNone:returnFalsereturn self.right.search(target)deffind_minimum_value(self):# if self.left is None: #recursive here# return self.value# min_value = self.left.find_minimum_value()# return min_value curr_node = selfwhile curr_node.left isnotNone: curr_node = curr_node.leftreturn curr_node.valueroot =BSTNode(10)# root.left = BSTNode(6)# root.right = BSTNode(12)root.insert(6)root.insert(7)root.insert(12)root.insert(5)root.insert(14)root.insert(8)print(f"minimum value in tree is: {root.find_minimum_value()}")print(f"does 8 exist? {root.search(8)}")print(f"does 8 exist? {root.search(7)}")print(f"does 8 exist? {root.search(15)}")
classBSTNode:def__init__(self,value): self.value = value self.left =None self.right =Nonedefinsert(self,value):# create a node for the new value new_node =BSTNode(value)# compare the node value to the self valueif ( new_node.value <= self.value ):# less then or equal to will all go to the left if any duplicats too# we add to the leftif self.left isNone: self.left = new_nodeelse: self.left.insert(value)else:# we add to the right# if space existsif self.right isNone: self.right = new_nodeelse: self.right.insert(value)defsearch(self,target):if target == self.value:returnTrue# check if value is less than self.valueif target < self.value:# look to the leftif self.left isNone:returnFalsereturn self.left.search(target)else:# look to the rightif self.right isNone:returnFalsereturn self.right.search(target)deffind_minimum_value(self):# if self.left is None: #recursive here# return self.value# min_value = self.left.find_minimum_value()# return min_value curr_node = selfwhile curr_node.left isnotNone: curr_node = curr_node.leftreturn curr_node.valueroot =BSTNode(10)# root.left = BSTNode(6)# root.right = BSTNode(12)root.insert(6)root.insert(7)root.insert(12)root.insert(5)root.insert(14)root.insert(8)print(f"minimum value in tree is: {root.find_minimum_value()}")print(f"does 8 exist? {root.search(8)}")print(f"does 8 exist? {root.search(7)}")print(f"does 8 exist? {root.search(15)}")
# Implement a Binary Search Tree (BST) that can insert values and check if# values are presentclassNode(object):def__init__(self,value): self.value = value self.left =None self.right =NoneclassBST(object):def__init__(self,root): self.root =Node(root)definsert(self,new_val):if(self.root.left==None):if(self.root.value>new_val): self.root.left =Node(new_val)elif(self.root.right==None):if(self.root.value<new_val): self.root.right =Node(new_val)else: current = self.rootwhile(current.left!=Noneor current.right!=None):if(current.value>new_val): current = current.leftelse: current = current.rightif(current.left==None): current.left =Node(new_val)else: current.right =Node(new_val)defsearch(self,find_val):if(self.root.left==Noneand self.root.right==Noneand self.root.value!=find_val):returnFalseelse: current = self.root val_possible =Truewhile(val_possible):if(current.value==find_val):returnTrueif(current.value<find_val): current = current.rightelse: current = current.leftif(current==None):returnFalseif(current.value<find_val and (current.right==Noneor current.right>find_val)):returnFalseif(current.value>find_val and (current.left==Noneor current.left<find_val)):returnFalse# Set up treetree =BST(4)# Insert elementstree.insert(2)tree.insert(1)tree.insert(3)tree.insert(5)# Check search# Should be Trueprint tree.search(4)# Should be Falseprint tree.search(6)
classNode(object):def__init__(self,value): self.value = value self.left =None self.right =NoneclassBinaryTree(object):def__init__(self,root): self.root =Node(root)defpreorder_search(self,start,find_val):"""Helper method - use this to create a recursive search solution."""if(start.value == find_val):returnTrueif(start.left!=None): left_result = self.preorder_search(start.left, find_val)else: left_result =Falseif(start.right!=Noneand left_result!=True): right_result = self.preorder_search(start.right, find_val)else: right_result =Falseif(left_result==Trueor right_result==True):returnTrueelse:returnFalsedefpreorder_print(self,start,traversal):"""Helper method - use this to create a recursive print solution.""" traversal +='-'+str(start.value) left_nums ='' right_nums =''if(start.left!=None): traversal = self.preorder_print(start.left, traversal)if(start.right!=None): traversal = self.preorder_print(start.right, traversal)return traversaldefsearch(self,find_val):"""Return True if the value is in the tree, return False otherwise."""return self.preorder_search(self.root, find_val)#print(self.preorder_search(self.root, find_val))defprint_tree(self):"""Print out all tree nodes as they are visited in a pre-order traversal.""" all_nodes = self.preorder_print(self.root, '') all_nodes = all_nodes[1:]return all_nodes# Set up treetree =BinaryTree(1)tree.root.left =Node(2)tree.root.right =Node(3)tree.root.left.left =Node(4)tree.root.left.right =Node(5)# Test search# Should be Trueprint(tree.search(4))# Should be Falseprint(tree.search(6))# Test print_tree# Should be 1-2-4-5-3print(tree.print_tree())
classBSTNode:def__init__(self,value): self.value = value self.left =None self.right =Nonedefinsert(self,value):# create a node for the new value new_node =BSTNode(value)# compare the node value to the self valueif ( new_node.value <= self.value ):# less then or equal to will all go to the left if any duplicats too# we add to the leftif self.left isNone: self.left = new_nodeelse: self.left.insert(value)else:# we add to the right# if space existsif self.right isNone: self.right = new_nodeelse: self.right.insert(value)defsearch(self,target):if target == self.value:returnTrue# check if value is less than self.valueif target < self.value:# look to the leftif self.left isNone:returnFalsereturn self.left.search(target)else:# look to the rightif self.right isNone:returnFalsereturn self.right.search(target)deffind_minimum_value(self):# if self.left is None: #recursive here# return self.value# min_value = self.left.find_minimum_value()# return min_value curr_node = selfwhile curr_node.left isnotNone: curr_node = curr_node.leftreturn curr_node.valueroot =BSTNode(10)# root.left = BSTNode(6)# root.right = BSTNode(12)root.insert(6)root.insert(7)root.insert(12)root.insert(5)root.insert(14)root.insert(8)print(f"minimum value in tree is: {root.find_minimum_value()}")print(f"does 8 exist? {root.search(8)}")print(f"does 8 exist? {root.search(7)}")print(f"does 8 exist? {root.search(15)}")
classNode:def__init__(self,value): self.value = value self.left =None self.right =NoneclassBST:def__init__(self): self.root =NonedefInsert(self,value): self.root = self.__InsertWrap(self.root, value)def__InsertWrap(self,x,value):if x ==None: x =Node(value)else:if value < x.value:# print("left") x.left = self.__InsertWrap(x.left, value)else:# print("right") x.right = self.__InsertWrap(x.right, value)return xdefInOrder(self):return self.__InOrder(self.root)def__InOrder(self,x):if x: self.__InOrder(x.left)print(x.value) self.__InOrder(x.right)defPreOrder(self):return self.__PreOrder(self.root)def__PreOrder(self,x):if x:print(x.value) self.__PreOrder(x.left) self.__PreOrder(x.right)defPostOrder(self):return self.__PostOrder(self.root)def__PostOrder(self,x):if x: self.__PostOrder(x.left) self.__PostOrder(x.right)print(x.value)defFindMin(self,x):while x.left !=None: x = x.leftreturn x.valuedefFindMax(self,x):while x.right !=None: x = x.rightreturn x.valuedefsuccessor(self,x):if x.right !=None: xx = x.rightwhile xx.left !=None: xx = xx.leftreturn xx.valuedefpredecessor(self,x):if x.left !=None: xx = x.leftwhile xx.right !=None: xx = x.rightreturn xx.valuedefHeight(self,x): y = self.__Height(x)return ydef__Height(self,x):if x ==None:return0else:return1+max(self.__Height(x.left), self.__Height(x.right))defdelete(self,node): x = self.root # rootNode, {Parent Node of desired Node}if node > x.value: y = x.right # desiredNode {Node to be delted} [iff on right]else: y = x.left # desiredNode [iff left]while y.value != node:# Searching the Node to deleteif node > y.value: x = x.right y = y.rightelse: x = x.left y = y.left# print("xr", x.right.value)# print("y", y.value) left = x.left # left of ParentNode right = x.right # right of ParentNode# Case 01if left.value == y.value and left.left isNoneand left.right isNone:# print("left", x.left.value) x.left =Noneelif right.value == y.value and right.left isNoneand right.right isNone:# print("right", x.right.value) x.right =None# Case 02elif ( left.value == y.valueand (left.left isnotNoneand left.right isNone)or (left.left isNoneand left.right isnotNone) ):if left.left isnotNone: child = left.leftelif left.right isnotNone: child = left.right x.left =None x.left = child# print("x",x.left.value)elif ( right.value == y.valueand (right.left isnotNoneand right.right isNone)or (right.left isNoneand right.right isnotNone) ):if right.left isnotNone: child = right.leftelif right.right isnotNone: child = right.right x.right =None x.right = child# Case 03elif left.value == y.value and left.left isnotNoneand left.right isnotNone: lChild = left.left rChild = left.rightmin= self.successor(left) self.delete(min) minNode =Node(min) minNode.left = lChild minNode.right = rChild x.left =None x.left = minNodeelif ( right.value == y.valueand right.left isnotNoneand right.right isnotNone ): lChild = right.left rChild = right.rightmin= self.successor(right) self.delete(min) minNode =Node(min) minNode.left = lChild minNode.right = rChild x.right =None x.right = minNode# Driver Codea =BST()a.Insert(20)a.Insert(40)a.Insert(12)a.Insert(1)root = a.rootprint("Getting Inorder:")a.InOrder()print("\nGetting Preorder:")a.PreOrder()print("\nGetting PostOrder:")a.PostOrder()print("\nGetting Height:")print(a.Height(root))print("\nGetting Minimum Node:")print(a.FindMin(root))print("\nGetting Maximum Node:")print(a.FindMax(root))print("\nGetting Successor:")print(a.successor(root))print("\nGetting Predecessor:")print(a.predecessor(root))print("\nDeleting a specific Node:")a.delete(12)print("\nTo cross-check deletion, printing preorder:")a.PreOrder()# In[ ]:
The following is the definition of Binary Search Tree(BST) according to Wikipedia
Binary Search Tree is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys lesser than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree. There must be no duplicate nodes.
The above properties of Binary Search Tree provides an ordering among keys so that the operations like search, minimum and maximum can be done fast. If there is no ordering, then we may have to compare every key to search for a given key.
Searching a key
For searching a value, if we had a sorted array we could have performed a binary search. Let’s say we want to search a number in the array what we do in binary search is we first define the complete list as our search space, the number can exist only within the search space. Now we compare the number to be searched or the element to be searched with the mid element of the search space or the median and if the record being searched is lesser we go searching in the left half else we go searching in the right half, in case of equality we have found the element. In binary search we start with ‘n’ elements in search space and then if the mid element is not the element that we are looking for, we reduce the search space to ‘n/2’ and we go on reducing the search space till we either find the record that we are looking for or we get to only one element in search space and be done with this whole reduction.
Search operation in binary search tree will be very similar. Let’s say we want to search for the number, what we’ll do is we’ll start at the root, and then we will compare the value to be searched with the value of the root if it’s equal we are done with the search if it’s lesser we know that we need to go to the left subtree because in a binary search tree all the elements in the left subtree are lesser and all the elements in the right subtree are greater. Searching an element in the binary search tree is basically this traversal in which at each step we will go either towards left or right and hence in at each step we discard one of the sub-trees. If the tree is balanced, we call a tree balanced if for all nodes the difference between the heights of left and right subtrees is not greater than one, we will start with a search space of **‘n’**nodes and when we will discard one of the sub-trees we will discard ‘n/2’ nodes so our search space will be reduced to ‘n/2’ and then in the next step we will reduce the search space to ‘n/4’ and we will go on reducing like this till we find the element or till our search space is reduced to only one node. The search here is also a binary search and that’s why the name binary search tree.
# A utility function to search a given key in BSTdefsearch(root,key):# Base Cases: root is null or key is present at rootif root isNoneor root.val == key:return root# Key is greater than root's keyif root.val < key:returnsearch(root.right,key)# Key is smaller than root's keyreturnsearch(root.left,key)
Illustration to search 6 in below tree:
Start from the root.
Compare the searching element with root, if less than root, then recurse for left, else recurse for right.
If the element to search is found anywhere, return true, else return false.
Insertion of a key
A new key is always inserted at the leaf. We start searching a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.
# Python program to demonstrate# insert operation in binary search tree# A utility class that represents# an individual node in a BSTclassNode:def__init__(self,key): self.left =None self.right =None self.val = key# A utility function to insert# a new node with the given keydefinsert(root,key):if root isNone:returnNode(key)else:if root.val == key:return rootelif root.val < key: root.right =insert(root.right, key)else: root.left =insert(root.left, key)return root# A utility function to do inorder tree traversaldefinorder(root):if root:inorder(root.left)print(root.val)inorder(root.right)# Driver program to test the above functions# Let us create the following BST# 50# / \# 30 70# / \ / \# 20 40 60 80r =Node(50)r =insert(r, 30)r =insert(r, 20)r =insert(r, 40)r =insert(r, 70)r =insert(r, 60)r =insert(r, 80)# Print inoder traversal of the BSTinorder(r)
Output
20
30
40
50
60
70
80
Illustration to insert 2 in below tree:
Start from the root.
Compare the inserting element with root, if less than root, then recurse for left, else recurse for right.
After reaching the end, just insert that node at left(if less than current) else right.
Time Complexity: The worst-case time complexity of search and insert operations is O(h) where h is the height of the Binary Search Tree. In the worst case, we may have to travel from root to the deepest leaf node. The height of a skewed tree may become n and the time complexity of search and insert operation may become O(n).
Insertion using loop:
****
Output
10 15 20 30 40 50 60
Some Interesting Facts:
Inorder traversal of BST always produces sorted output.
We can construct a BST with only Preorder or Postorder or Level Order traversal. Note that we can always get inorder traversal by sorting the only given traversal.
When balanced, a BST provides lightning-fast O(log(n)) insertions, deletions, and lookups.
Binary search trees are pretty simple. An ordinary BST, unlike a balanced tree like a red-black tree, requires very little code to get running.
Cons of a BST
Slow for a brute-force search. If you need to iterate over each node, you might have more success with an array.
When the tree becomes unbalanced, all fast O(log(n)) operations quickly degrade to O(n).
Since pointers to whole objects are typically involved, a BST can require quite a bit more memory than an array, although this depends on the implementation.
Implementing a BST in Python
Step 1 – BSTNode Class
Our implementation won’t use a Tree class, but instead just a Node class. Binary trees are really just a pointer to a root node that in turn connects to each child node, so we’ll run with that idea.
We’ll allow a value (key) to be provided, but if one isn’t provided we’ll just set it to None. We’ll also initialize both children of the new node to None.
Step 2 – Insert
We need a way to insert new data. The insert method is as follows:
If the node doesn’t yet have a value, we can just set the given value and return. If we ever try to insert a value that also exists, we can also simply return as this can be considered a noop. If the given value is less than our node’s value and we already have a left child then we recursively call insert on our left child. If we don’t have a left child yet then we just make the given value our new left child. We can do the same (but inverted) for our right side.
Step 3 – Get Min and Get Max
defget_min(self): current = selfwhile current.left isnotNone: current = current.leftreturn current.valdefget_max(self): current = selfwhile current.right isnotNone: current = current.rightreturn current.valCode language:Python (python)
getMin and getMax are useful helper functions, and they’re easy to write! They are simple recursive functions that traverse the edges of the tree to find the smallest or largest values stored therein.
The delete operation is one of the more complex ones. It is a recursive function as well, but it also returns the new state of the given node after performing the delete operation. This allows a parent whose child has been deleted to properly set it’s left or right data member to None.
Step 5 – Exists
The exists function is another simple recursive function that returns True or False depending on whether a given value already exists in the tree.
def exists(self, val):
if val == self.val:
return True
if val < self.val:
if self.left == None:
return False
return self.left.exists(val)
if self.right == None:
return False
return self.right.exists(val)Code language: Python (python)
Step 6 – Inorder
It’s useful to be able to print out the tree in a readable format. The inorder method print’s the values in the tree in the order of their keys.
Where would you use a binary search tree in real life?
There are many applications of binary search trees in real life, and one of the most common use-cases is in storing indexes and keys in a database. For example, in MySQL or PostgresQL when you create a primary key column, what you’re really doing is creating a binary tree where the keys are the values of the column, and those nodes point to database rows. This lets the application easily search database rows by providing a key. For example, getting a user record by the email primary key.
There are many applications of binary search trees in real life, and one of the most common use cases is storing indexes and keys in a database. For example, when you create a primary key column in MySQL or PostgresQL, you create a binary tree where the keys are the values of the column and the nodes point to database rows. This allows the application to easily search for database rows by specifying a key, for example, to find a user record using the email primary key.
Other common uses include:
Pathfinding algorithms in videogames (A*) use BSTs
File compression using a Huffman encoding scheme uses a binary search tree
Rendering calculations – Doom (1993) was famously the first game to use a BST
Compilers for low-level coding languages parse syntax using a BST
Almost every database in existence uses BSTs for key lookups
Example Binary Tree
Visual Aid
Example Code
classTreeNode {constructor(val) {this.val = val;this.left =null;this.right =null; }}let a =newTreeNode("a");let b =newTreeNode("b");let c =newTreeNode("c");let d =newTreeNode("d");let e =newTreeNode("e");let f =newTreeNode("f");a.left = b;a.right = c;b.left = d;b.right = e;c.right = f;
Terms
tree - graph with no cycles
binary tree - tree where nodes have at most 2 nodes
root - the ultimate parent, the single node of a tree that can access every other node through edges; by definition the root will not have a parent
internal node - a node that has children
leaf - a node that does not have any children
path - a series of nodes that can be traveled through edges - for example A, B, E is a path through the above tree
Search Patterns
Breadth First Search - Check all nodes at a level before moving down a level
Think of this of searching horizontally in rows
Depth First Search - Check the depth as far as it goes for one child, before
moving on to the next child.
Think of this as searching vertically in diagonals
Pre-Order Traversal - Access the data of the current node, recursively visit the left sub tree, recursively visit the right sub tree
All the way to the left, top down, going right after other options have already been logged.
In-Order Traversal - Recursively visit the left sub tree, access the data of the current node, recursively visit the right sub tree
In the order they were the "current root", the actual return order of the recursive calls.
Post-Order Traversal - Recursively visit the left sub tree, recursively visit the right sub tree, access the data of the current node.
Starting with the bottom most nodes working up through the tree
Constraints
Binary trees have at most two children per node
Given any node of the tree, the values on the left must be strictly less than that node
Given any node of the tree, the values on the right must be strictly greater than or equal to that node
Given these constraints a binary tree is necessarily a sorted data structure
The worst binary trees devolve into a linked list, the best are height balanced (think branching).
PseudoCode For Insertion
Create a new node
Start at the root
Check if there is a root
If not the root becomes the new node
If there is a root check if the value of the new node is equal to, greater then, or less then the value of the root
If it is greater or equal to
Check to see if there is a node to the right
If there is, move to the new node and continue with the node to the right as the subtree root
If there is not, add the new node as the right property of the current node
If it is smaller
Check to see if there is a node to the left
If there is, move to the new node and continue with the node to the left as the subtree root
If there is not, add the new node as the left property of the current node
PseudoCode For Search Of A single Item
Start at the root
Check if there is a root
If not, there is nothing in the tree, so the search is over
If there is a root, check if the value of the root is equal to, greater then, or less then the value were looking for;
If it is equal to the value
We found what we are searching for
If it is less than the value
Check to see if there is a node to the left
If there isn't
the value isn't in our tree
If there is
repeat these steps with the node to the left as the new subtree root
If it is greater than the value
Check to see if there is a node to the right
If there isn't
the value isn't in our tree
If there is
repeat these steps with the node to the right as the new subtree root
PseudoCode For Breadth First Search Traversal
Create a queue class or use an array
Create a variable to store the values of the nodes visited
Place the root in the queue
Loop as many times as there are items in the queue
Dequeue a node
If there is a left value to the node dequeued, add it to the queue
If there is a right value to the node dequeued, add it to the queue
Push the nodes value into the variable that stores nodes visited
PseudoCode For Depth First Search Traversal
Pre-Order
Iterative
Create a stack class or use an array
Push the root into the stack
Create a variable to store the values of the nodes visited
Do this as long as there is something on the stack
Pop a node from the stack
Push that nodes value into the variable that stores nodes visited.
If there is a node to the right push it into the stack
If there is a node to the left push it into the stack
Return the variable storing the values
Recursive
Create a variable to store the current root
Push the value of current root to the variable storing the values
If the current root has a left propety call the function on that the left property
If the current root has a right propety call the function on that the right property
Spread the current root, the left values, and the right values
In-Order
Iterative
Create a stack class or use an array
Create a variable to store the current root
Create a variable to store the values of the nodes visited
Create a loop
While the current root exists
push the current root to the call stack
current root is equal to the left of current root
if the stack is empty break out of the loop
set a variable to equal the popped value of the stack
push that variable into the variable that stores values
set the current root to the right of the current loop
Return the variable storing the values
Recursive
Create a variable to store the current root
Push the value of current root to the variable storing the values
If the current root has a left propety call the function on that the left property
If the current root has a right propety call the function on that the right property
Spread the the left values, current root ,and the right values
Post-Order
Iterative
Haven't figured this one out yet.
Recursive
Create a variable to store the current root
Push the value of current root to the variable storing the values
If the current root has a left propety call the function on that the left property
If the current root has a right propety call the function on that the right property
Spread the the left values, the right values, and current root