Simple Traversals in Binary Trees

-
A common data structure used in algorithms is a tree (which actually should have been named “pyramid” since a tree has its root at the bottom, not at the top) and traversing a tree becomes one of the fundamentals techniques in computer science. For a simple binary tree, there are basically three well-known techniques for traversing the tree:
·         Pre-Order: in which you perform some computation against the current node, then recursively perform the computation for the left and then the right nodes
·         In-Order: in which you perform some computation against the left node (recursively), then against the current node then recursively against the right node (recursively)
·         Post-Order: in which you perform some computation against the left node (recursively), then against the right node (recursively) and then against the current node
The following problem can be solved with any of the traversals above: given a binary tree, determine whether the tree is a Binary Search Tree (BST). A BST is defined (at least that’s the definition we’re adopting here) as a binary tree where the value of any node is greater than or equal to any value in its left sub-tree, and less than or equal to any value of its right sub-tree.
A pre-order traversal can be done, but requires a double traversal of the tree (notice that you need to check the entire sub-tree, not only the current children), hence the cost for the pre-order solution is O(N^2) where N is the number of nodes. The post-order seems simpler to understand but requires that we keep track of the max & min values for each sub-tree. It is however efficient: O(N). The in-order also achieves a O(N) time complexity, but it does not come to me as intuitive as the post-order solution. Basically the in-order leverages the fact that if you read the values of the BST from left to right you’ll have a total order of the elements. In addition, to print the tree there is another traversal which is a per-level traversal making use of a queue (instead of a stack, so no recursion there), doing a Breadth-First Search (BFS) instead of the {Pre, In, Post}-Order traversals, which are all Depth-First Search (DFS). Code is below:

Tree.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace IsBST
{
    class Tree
    {
        class Node
        {
            public int value;
            public Node left;
            public Node right;

            public Node(int value)
            {
                this.value = value;
                this.left = null;
                this.right = null;
            }
        }

        class QueueElement
        {
            public Node currentNode;
            public Node parentNode;
            public int level;
            public string relativePositionToParent; //L or R

            public QueueElement(Node currentNode,
                                Node parentNode,
                                int level,
                                string relativePositionToParent)
            {
                this.currentNode = currentNode;
                this.parentNode = parentNode;
                this.level = level;
                this.relativePositionToParent = relativePositionToParent;
            }
        }

        private Node root;

        public Tree()
        {
            this.root = null;
        }

        public void Print()
        {
            if (this.root == null)
            {
                Console.WriteLine("Tree is empty!");
                return;
            }

            Queue<QueueElement> queue = new Queue<QueueElement>();
            int currentLevel = 0;
            QueueElement qe = new QueueElement(this.root, null, 0, "");
            queue.Enqueue(qe);
            while (queue.Count > 0)
            {
                qe = queue.Dequeue();
                if (qe.level != currentLevel)
                {
                    Console.WriteLine();
                    currentLevel = qe.level;
                }
                Console.Write("{0}{1}({2}) ", qe.currentNode.value, qe.relativePositionToParent, (qe.parentNode==null)?"root":qe.parentNode.value.ToString());

                if (qe.currentNode.left != null)
                {
                    queue.Enqueue(new QueueElement(qe.currentNode.left, qe.currentNode, qe.level+1, "L"));
                }
                if (qe.currentNode.right != null)
                {
                    queue.Enqueue(new QueueElement(qe.currentNode.right, qe.currentNode, qe.level+1, "R"));
                }
            }
            Console.WriteLine();
        }

        public void AddValueBST(int value)
        {
            if (this.root == null)
            {
                this.root = new Node(value);
            }
            else
            {
                Node currentNode = this.root;
                while (currentNode != null)
                {
                    if (value < currentNode.value)
                    {
                        if (currentNode.left == null)
                        {
                            currentNode.left = new Node(value);
                            return;
                        }
                        else
                        {
                            currentNode = currentNode.left;
                        }
                    }
                    else
                    {
                        if (currentNode.right == null)
                        {
                            currentNode.right = new Node(value);
                            return;
                        }
                        else
                        {
                            currentNode = currentNode.right;
                        }
                    }
                }
            }
        }

        public void AddValueRandomly(int value)
        {
            if (this.root == null)
            {
                this.root = new Node(value);
            }
            else
            {
                Node currentNode = this.root;
                while (currentNode != null)
                {
                    string guid = Guid.NewGuid().ToString();
                    int seed = 0;
                    foreach (char c in guid)
                    {
                        int number = 0;
                        if (Int32.TryParse(c.ToString(), out number))
                        {
                            seed = (int)((10L * seed + number) % Int32.MaxValue);
                        }
                    }

                    int coinToss = seed % 2;
                    switch (coinToss)
                    {
                        case 0:
                            if (currentNode.left == null)
                            {
                                currentNode.left = new Node(value);
                                return;
                            }
                            else
                            {
                                currentNode = currentNode.left;
                            }
                            break;
                        case 1:
                            if (currentNode.right == null)
                            {
                                currentNode.right = new Node(value);
                                return;
                            }
                            else
                            {
                                currentNode = currentNode.right;
                            }
                            break;
                    }
                }
            }
        }

        public bool IsBST_PreOrder()
        {
            return _IsBST_PreOrder(this.root);
        }
        public bool IsBST_PostOrder()
        {
            int max = 0;
            int min = 0;
            return _IsBST_PostOrder(this.root, ref max, ref min);
        }
        public bool IsBST_InOrder()
        {
            int previousValue = Int32.MinValue;
            return _IsBST_InOrder(this.root, ref previousValue);
        }

        private bool _IsBST_InOrder(Node node,
                                    ref int previousValue)
        {
            if (node == null)
            {
                return true;
            }

            //Process left
            if (!_IsBST_InOrder(node.left, ref previousValue))
            {
                return false;
            }

            //Process current
            if (node.value < previousValue)
            {
                return false;
            }
            previousValue = node.value;

            //Process right
            return _IsBST_InOrder(node.right, ref previousValue);
        }

        private bool _IsBST_PostOrder(Node node,
                                      ref int max,
                                      ref int min)
        {
            if (node == null)
            {
                max = Int32.MinValue;
                min = Int32.MaxValue;
                return true;
            }

            //Process left
            int lMax = Int32.MinValue;
            int lMin = Int32.MaxValue;
            if (!_IsBST_PostOrder(node.left,
                                  ref lMax,
                                  ref lMin))
            {
                return false;
            }

            //Process right
            int rMax = Int32.MinValue;
            int rMin = Int32.MaxValue;
            if (!_IsBST_PostOrder(node.right,
                                  ref rMax,
                                  ref rMin))
            {
                return false;
            }

            //Process current
            if (node.value < lMax ||
                node.value > rMin)
            {
                return false;
            }

            max = Math.Max(Math.Max(lMax, rMax), node.value);
            min = Math.Min(Math.Min(lMin, rMin), node.value);
           
            return true;
        }

        private bool _IsBST_PreOrder(Node node)
        {
            if (node == null)
            {
                return true;
            }

            //Process current
            if (!_CompareAllElements(node.left, node.value, "greater than or equal") ||
                !_CompareAllElements(node.right, node.value, "less than or equal"))
            {
                return false;
            }

            //Process left
            //Process right
            return _IsBST_PreOrder(node.left) && _IsBST_PreOrder(node.right);
        }

        private bool _CompareAllElements(Node node,
                                         int value,
                                         string comparison)
        {
            if (node == null)
            {
                return true;
            }

            //Process current
            switch (comparison)
            {
                case "greater than":
                    if (value <= node.value)
                    {
                        return false;
                    }
                    break;
                case "greater than or equal":
                    if (value < node.value)
                    {
                        return false;
                    }
                    break;
                case "less than":
                    if (value >= node.value)
                    {
                        return false;
                    }
                    break;
                case "less than or equal":
                    if (value > node.value)
                    {
                        return false;
                    }
                    break;
            }

            //Process left
            //Process right
            return _CompareAllElements(node.left, value, comparison) && _CompareAllElements(node.right, value, comparison);
        }
    }
}

Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace IsBST
{
    class Program
    {
        static void Main(string[] args)
        {
            int nNodes = 0;
            if (args.Length == 0 ||
                !Int32.TryParse(args[0], out nNodes))
            {
                Console.WriteLine("Usage: IsBST.exe <number of nodes in the trees>");
                return;
            }

            Tree treeBST = new Tree();
            Tree treeRandom = new Tree();

            Random rd = new Random();
            for (int i = 0; i < nNodes; i++)
            {
                treeBST.AddValueBST(rd.Next(0, 100));
                treeRandom.AddValueRandomly(rd.Next(0, 20));
            }
            Console.WriteLine("BST Tree:");
            treeBST.Print();
            Console.WriteLine();
            Console.WriteLine("Random Tree:");
            treeRandom.Print();
            Console.WriteLine();
            Console.WriteLine("Is the BST Tree a BST (Pre-Order): {0}", treeBST.IsBST_PreOrder());
            Console.WriteLine("Is the BST Tree a BST (Post-Order): {0}", treeBST.IsBST_PostOrder());
            Console.WriteLine("Is the BST Tree a BST (In-Order): {0}", treeBST.IsBST_InOrder());
            Console.WriteLine("Is the Random Tree a BST (Pre-Order): {0}", treeRandom.IsBST_PreOrder());
            Console.WriteLine("Is the Random Tree a BST (Post-Order): {0}", treeRandom.IsBST_PostOrder());
            Console.WriteLine("Is the Random Tree a BST (In-Order): {0}", treeRandom.IsBST_InOrder());
        }
    }
}

Comments

  1. Balaji GururajanJuly 28, 2012 at 12:52 PM

    Hi Marcelo

    You should add this code to http://github.com. (This is a public source control where code can be shared) They have nice integration with vs2013 as well as a source control.
    Also, you should try Glee library (http://research.microsoft.com/en-us/downloads/f1303e46-965f-401a-87c3-34e1331d32c5/default.aspx) from MSR. It allows drawing tree/graph in UI with circles and lines

    ReplyDelete
    Replies
    1. Marcelo M De BarrosJuly 30, 2012 at 10:47 AM

      Ah, very nice. I've always had problems printing out a b-tree in a nice format. Will take a look, thanks Balaji!

      Delete

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

-
Image
If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul
Read more

Prompt Engineering and LeetCode

-
Image
With AI it becomes super interesting to try to "guide" it to solve a coding (LeetCode) problem. An example would be this one here:  The Knight’s Tour - LeetCode 2664. The Knight’s Tour Medium 11 0 Add to List Share Given two positive integers  m  and  n  which are the height and width of a  0-indexed  2D-array  board , a pair of positive integers  (r, c)  which is the starting position of the knight on the board. Your task is to find an order of movements for the knight, in a manner that every cell of the  board  gets visited  exactly  once (the starting cell is considered visited and you  shouldn't  visit it again). Return  the array   board   in which the cells' values show the order of visiting the cell starting from 0 (the initial place of the knight). Note that a  knight  can  move  from cell  (r1, c1)  to cell  (r2, c2)  if  0 <= r2 <= m - 1  and  0 <= c2 <= n - 1  and  min(abs(r1 - r2), abs(c1 - c2)) = 1  and  max(abs(r1 - r2), abs(c1 - c2)) = 2 .  
Read more

ProjectEuler Problem 719 (some hints, but no spoilers)

-
Image
Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today:  https://projecteuler.net/problem=719 Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo
Read more