C# Binary search tree

Question

I implemented binary search tree. What do you think about my code? How could i optimize it? Where are my major mistakes? I am not asking only about BST but about my coding style in general, using of classes, methods, naming...

using System;
using System.Collections.Generic;
/// <summary>
/// My implementation of BST. It has two classes. Node & BSTree.
/// </summary>
namespace BinarySearchTree
{
    class Program
    {
        static void Main(string[] args)
        {

            BSTree bst = new BSTree(new Node(20));
            bst.Insert(15);
            bst.Insert(25);
            bst.Insert(18);
            bst.Insert(10);
            bst.Insert(new Node(19));
            bst.Insert(new Node(16));
            bst.Insert(new Node(17));
            /*
                  20
                 /  \
                15  25
               /  \
              10  18
                 /  \
                16  19
                  \
                  17

            */

            bst.PrintTraversedTree(BSTree.TreeTraversalForm.BreathFirstSearch);
            bst.Delete(15);

            /*
                 20
                /  \
               16  25
              /  \
             10  18
                /  \
               17  19

           */

            bst.PrintTraversedTree(BSTree.TreeTraversalForm.BreathFirstSearch);

            Console.WriteLine("Searching for node...");
            Node devetnajst = bst.BinarySearch(19);
            if (devetnajst != null)
                Console.WriteLine($"Node value: {devetnajst.value}");
            else
                Console.WriteLine("Node not found!");

            Console.WriteLine("Searching for node...");
            Node stNiVDrevesu = bst.BinarySearch(23);
            if(stNiVDrevesu!=null)
                Console.WriteLine($"Node value: {stNiVDrevesu.value}");
            else
                Console.WriteLine("Node not found!");

            Console.WriteLine("Searching for node...");
            Node someNode = bst.BinarySearchI(17);
            if (someNode != null)
                Console.WriteLine($"Node value: {someNode.value}");
        }
    }

    /// <summary>
    /// class Node represents nodes of the binary three.
    /// </summary>
    class Node
    {
        public Node(int value)
        {
            this.value = value;
        }
        public int value { get; set; }
        public Node left { get; set; } = null;
        public Node right { get; set; } = null;

        /// <summary>
        /// Returns true if node is Leaf
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public bool isLeaf()
        {
            if (this.left == null && this.right == null)
                return true;
            else
                return false;
        }

        /// <summary>
        /// Returns true if this is left child of parent
        /// </summary>
        /// <param name="node"></param>
        /// <param name="parent"></param>
        /// <returns></returns>
        public bool isLeftChildOf(Node parent)
        {
            if (this == parent.left)
                return true;
            else
                return false;
        }

        /// <summary>
        /// Returns true if this is right child of parent
        /// </summary>
        /// <param name="node"></param>
        /// <param name="parent"></param>
        /// <returns></returns>
        public bool isRightChildOf(Node parent)
        {
            if (this == parent.right)
                return true;
            else
                return false;
        }

        /// <summary>
        /// return true if node has only one child
        /// </summary>
        /// <returns></returns>
        public bool hasOnlyOneChild()
        {
            if (!this.isLeaf() && (this.left == null || this.right == null))
                return true;
            else
                return false;
        }

    }

    /// <summary>
    /// class BSTree represent Binary Search Tree. 
    /// </summary>
    class BSTree
    {
        Node _root=null; // tree root
        int[] _treeTraversal; //three traversal -- dynamic programing
        int _nodeCounter=0; //nr of nodes - used to declare _treeTraversal size
        int _treeTraversalIndex = 0; //used to position node in array _treeTraversal
        int _currentTraverseForm = -1; //if -1 -> no valid traverse of tree 

        /// <summary>
        /// Constructor
        /// </summary>
        /// <param name="root"></param>
        public BSTree(Node root) {
            _root = root;
            _nodeCounter++;
        }

        /// <summary>
        /// Constructor
        /// </summary>
        /// <param name="rootValue"></param>
        public BSTree(int rootValue)
        {
            _root = new Node(rootValue);
            _nodeCounter++;
        }

        /// <summary>
        /// Insert value into Tree
        /// </summary>
        /// <param name="value"></param>
        public void Insert(int value)
        {
            Insert(new Node(value));
        }

        /// <summary>
        /// Insert Node into tree
        /// </summary>
        /// <param name="node">Node to be inserted.</param>
        /// <param name="root"></param>
        public void Insert(Node node, Node root=null)
        {
            if (root == null)
            {
                root = _root; // if no root is specified use tree root
            }

            if (node.value == root.value)
            {
                Console.WriteLine($"Unable to insert! Value {node.value} allready exist!");
                return;
            }

            if (node.value<root.value)
            {
                if (root.left == null)
                {
                    root.left = node;
                    _nodeCounter++;
                    _currentTraverseForm = -1; // when you insert new node current stored traverse is not valid anymore
                }
                else
                {
                    Insert(node, root.left);
                }
            }
            else
            {
                if (root.right == null)
                {
                    root.right = node;
                    _nodeCounter++;
                    _currentTraverseForm = -1;
                }
                else
                {
                    Insert(node, root.right);
                }
            }

        }

        /// <summary>
        /// Binary Search throught the tree for value - recursive
        /// </summary>
        /// <param name="value">searched value</param>
        /// <param name="root"></param>
        /// <returns>Node if found, otherwise returns null</returns>
        public Node BinarySearch(int value, Node root = null)
        {
            if (root == null)
            {
                root = _root;
            }

            if (value == root.value)
            {
                return root;
            }

            if (value < root.value)
            {
                if (root.left != null)
                {
                    return BinarySearch(value, root.left);
                }
                else
                {
                    return null;
                }
            }
            else
            {
                if (root.right != null)
                {
                    return BinarySearch(value, root.right);
                }
                else
                {
                    return null;
                }
            }


        }

        /// <summary>
        /// Binary Search Iterative
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        public Node BinarySearchI(int value)
        {
            Node node = _root;

            for (int i = 0; i < _nodeCounter;i++) {
                if (value == node.value)
                {
                    return node;
                }
                else if (value < node.value && node.left != null)
                {
                    node = node.left;
                }
                else if (node.right != null)
                {
                    node = node.right;
                }
                else
                {
                    Console.WriteLine("Value not found!");
                    break;
                }

            }
            return null;
        }



        /// <summary>
        /// get Next inorder - smalest from right subtree
        /// </summary>
        /// <param name="root"></param>
        public Node GetNextInorder(Node node)
        {

            return Smalest(node.right);
        }

        /// <summary>
        /// get smallest from from root - most left in subtree or tree
        /// </summary>
        /// <param name="root"></param>
        private Node Smalest(Node root)
        {

            Node minNode = root.left;

            while (root.left != null)
            {
                root = root.left;
                minNode = root;
            }

            return minNode;
        }

        /// <summary>
        /// Deletes the node
        /// </summary>
        /// <param name="node"></param>
        /// <param name="root"></param>

        public void Delete(Node node, Node root = null)
        {
            if (node == null) {
                Console.WriteLine("Please enter valid node!");
                return;
            }

            if (root == null)
            {
                root = _root;
                Console.WriteLine($"Deleting node: {node.value}");
            }

            //if node is child of root->we found parents of child 
            if (node.isLeftChildOf(root) || node.isRightChildOf(root)) 
            {
                if (node.isLeaf()) // if is Leaf just remove it - remove reference at parrent
                {
                    if (node.isLeftChildOf(root))
                        root.left = null;
                    else
                        root.right = null;

                    _currentTraverseForm = -1;
                    _nodeCounter--;
                }
                else if (node.hasOnlyOneChild()) // if only one child replace node with child
                {
                    if (node.left == null)
                    {
                        node.value = node.right.value;
                        node.left = node.right.left;
                        node.right = node.right.right;
                    }
                    else
                    {
                        node.value = node.left.value;
                        node.left = node.left.left;
                        node.right = node.left.right;
                    }

                    _currentTraverseForm = -1;
                    _nodeCounter--;

                }
                else //else replace node with next in-order.
                {
                    Node tmpNode = GetNextInorder(node);
                    node.value = tmpNode.value;
                    Delete(tmpNode, node);

                    _currentTraverseForm = -1;
                }

            }
            else // else we need to dig deeper to the left or right
            {
                if (root.left != null && node.value < root.value)
                    Delete(node, root.left);
                else if(root.right!=null)
                    Delete(node, root.right);
            }

        }

        /// <summary>
        /// Deletes the node using value and binary search
        /// </summary>
        /// <param name="value"></param>
        /// <param name="root"></param>
        public void Delete(int value, Node root = null)
        {
            Delete(BinarySearch(value));
        }

        /// <summary>
        /// enum specifaing posible tree traversal forms
        /// DFS - Depth-first search
        /// </summary>
        public enum TreeTraversalForm
        {
            DFSpreorder,
            DFSinorder,
            DFSoutorder,
            DFSpostorder,
            BreathFirstSearch
        };

        /// <summary>
        /// Maps the tree traversal form with appropriate method
        /// </summary>
        /// <param name="traversalForm"></param>
        /// <returns></returns>
        public int[] TraverseTree(TreeTraversalForm traversalForm)
        {

            //if tree is already traversed -> dont do it again
            if ((int)traversalForm != _currentTraverseForm)
            {
                switch (traversalForm)
                {
                    case TreeTraversalForm.DFSinorder:
                        this.Inorder();
                        break;
                    case TreeTraversalForm.DFSoutorder:
                        this.Outorder();
                        break;
                    case TreeTraversalForm.DFSpostorder:
                        this.Postorder();
                        break;
                    case TreeTraversalForm.DFSpreorder:
                        this.Preorder();
                        break;
                    case TreeTraversalForm.BreathFirstSearch:
                        this.BreathFirstSearch();
                        break;
                    default:
                        Console.WriteLine("Unknown form!");
                        break;
                }
            }

            return _treeTraversal;
        }

        /// <summary>
        /// Prints traversed tree to Console
        /// </summary>
        /// <param name="traversalForm"></param>
        public void PrintTraversedTree(TreeTraversalForm traversalForm)
        {

            //if tree is already traversed -> dont do it again
            if ((int)traversalForm != _currentTraverseForm)
            {
                this.TraverseTree(traversalForm);
            }

            Console.Write(traversalForm.ToString() + ": ");
            foreach (int val in _treeTraversal)
            {
                Console.Write($"{val} ");
            }
            Console.WriteLine();
        }

        /// <summary>
        /// Creates DFS - Pre-order traverse and stors it in _treeTraversal
        /// </summary>
        /// <param name="root"></param>
        void Preorder(Node root = null)
        {
            if (root == null)
            {
                root = _root;
                _treeTraversal = new int[_nodeCounter];
                _treeTraversalIndex = 0;
                _currentTraverseForm = (int)TreeTraversalForm.DFSpreorder;
            }

            _treeTraversal[_treeTraversalIndex] = root.value;
            _treeTraversalIndex++;

            if (root.left != null)
                Preorder(root.left);

            if (root.right != null)
                Preorder(root.right);
        }

        /// <summary>
        /// Creates DFS - In-order traverse and stors it in _treeTraversal
        /// </summary>
        /// <param name="root"></param>
        void Inorder(Node root = null)
        {
            if (root == null)
            {
                root = _root;
                _treeTraversal = new int[_nodeCounter];
                _treeTraversalIndex = 0;
                _currentTraverseForm = (int)TreeTraversalForm.DFSinorder;
            }


            if (root.left != null)
                Inorder(root.left);

            _treeTraversal[_treeTraversalIndex] = root.value;
            _treeTraversalIndex++;

            if (root.right != null)
                Inorder(root.right);
        }

        /// <summary>
        /// Creates DFS - Post-order traverse and stors it in _treeTraversal
        /// </summary>
        /// <param name="root"></param>
        void Postorder(Node root = null)
        {
            if (root == null)
            {
                root = _root;
                _treeTraversal = new int[_nodeCounter];
                _treeTraversalIndex = 0;
                _currentTraverseForm = (int)TreeTraversalForm.DFSpostorder;
            }


            if (root.left != null)
                Postorder(root.left);

            if (root.right != null)
                Postorder(root.right);

            _treeTraversal[_treeTraversalIndex] = root.value;
            _treeTraversalIndex++;
        }

        /// <summary>
        /// Creates DFS - Out-order traverse and stors it in _treeTraversal
        /// </summary>
        /// <param name="root"></param>
        void Outorder(Node root = null)
        {
            if (root == null)
            {
                root = _root;
                _treeTraversal = new int[_nodeCounter];
                _treeTraversalIndex = 0;
                _currentTraverseForm = (int)TreeTraversalForm.DFSoutorder;
            }


            if (root.right != null)
                Outorder(root.right);

            _treeTraversal[_treeTraversalIndex] = root.value;
            _treeTraversalIndex++;

            if (root.left != null)
                Outorder(root.left);

        }

        /// <summary>
        /// Creates BFS - BreathFirstSearch traverse and stors it in _treeTraversal
        /// </summary>
        /// <param name="root"></param>
        void BreathFirstSearch(Node root = null)
        {
            if (root == null)
            {
                root = _root;
                _treeTraversal = new int[_nodeCounter];
                _treeTraversalIndex = 0;
                _currentTraverseForm = (int)TreeTraversalForm.BreathFirstSearch;

                _treeTraversal[_treeTraversalIndex] = root.value;
                _treeTraversalIndex++;
            }



            if (root.left != null)
            {
                _treeTraversal[_treeTraversalIndex] = root.left.value;
                _treeTraversalIndex++;
            }

            if (root.right != null)
            {
                _treeTraversal[_treeTraversalIndex] = root.right.value;
                _treeTraversalIndex++;
            }

            if (root.left != null)
                BreathFirstSearch(root.left);
            if (root.right != null)
                BreathFirstSearch(root.right);
        }
    }
}

VisualMelon · Accepted Answer · 2019-04-27 19:05:13Z

API

I really don't like the returning of the cached value as int[]. Anyone who recieves this return value is free to modify it, and there is no indication that it might be returned multiple times. At the very least, this code should be returning an immutable view of the array (e.g. an IReadOnlyList<int>), but if you really want to cache the results, then I would probably clone the array every time it was returned.

I don't like that you have public methods which take the root nodes defaulted as null (e.g. Delete). It would be nicer to make these methods private (so they can't be used) and static (so they know the minimum necessary and can't accidently mess with state) without a default parameter, and provide public members which don't take a parameter, and pass the root to the parameterised methods. Of course, you may want to deliberately expose the capability, but in that case, it is possible for one BSTree to operate on another tree's Nodes, and that is a receipe for confusion.

Generally, you are opening a serious can of worms when you expose implementation details like your Node class to the world, because anyone can modify a Node from the BST and ruin the data-structure: if you don't need to expose this information, then do not. If you want a data-structure that can support crazy usage, then you need to document it is as such. Any Nodes that have been handed out may be invalidated the moment you perform any operation on the BST.

You might consider making your class generic, so that it can store any value, and not just integers.

Correctness

The BreathFirstSearch isn't a breadth-first search.

This code in Delete looks suspect:

node.value = node.left.value;
node.left = node.left.left;
node.right = node.left.right;

Smalest is over complicated, keeping track of the same piece of state in 2 variables. It looks wrong, since it will return null if the root has no left-child. This causes Delete to crash under some cirsumstances (e.g. replace the first call to Delete in your code with Delete(18): boom.

Delete is also unable to delete the root node.

Error handling

If a method is unable to perform it's task, it should be throwing an exception; it shouldn't not print to the console and it should not return cleanly. In Insert, for example, if trying to add the same value twice is explicitly forbidden, it should throw an exception. If it is allowed, and you just want to ignore this, then you should just return cleaning. A general purpose component should not be printing to the console: you have no idea what job it has in an application.

In TraverseTree, an unrecognise traversal method is surely exception worthy: it certainly does not warrant returning whatever _treeTraversal happens to contain. Throwing an exception forces the consuming code to address the problem up-front (which is good, because ignoring it makes no sense), stops there code proceeding under a false pretense (which may lead to data corruption), and gives them lots of useful information about where the program logic went wrong (e.g. stack trace, and more if there is a debugger handy).

Printing

Similarly, PrintTraversedTree assumes that the console is a good place to put stuff: much better, if you want to provide this functionality, to have PrintTraversedTree take a TextWriter, so that the caller can decide where the stuff should be printed. I'd question whether this method should be a member of the class: it has no concern with the classes internal state, and could just as well be a static method elsewhere.

Delete even tells the console what it is doing: why? If the calling code wants to tell the console that it is delete a node, then it can do that itself: the BST should stick to being a BST.

Naming and Spelling

You might consider following microsoft's naming conventions (because everyone else does) for public members and types, which is to use ProperCamelCase for everything. Node.value, for example, would be Node.Value; isLeaf would be IsLeaf, etc.

There are numerous spelling errors in member names, variable names, inline documentation (nice to see, though it could be more useful), and comments.

I would consider renaming Smalest to FindSmallestDescendent or FindLeftmostDescendent, so that is clearer what is does.

Don't Repeat Yourself

The code to initialise _treeTraversal appears in 5 methods, and is every time identical. It should be in its own method, and need only called once from Traverse.

This appears all over the place:

_treeTraversal[_treeTraversalIndex] = /*something*/;
_treeTraversalIndex++;

This could be another little method: it would make the code much tidier if it had calls to Append(int) instead of this everywhere, which hides away the complexity of the task, and makes the intention clear.

I'd also replace _currentTraverseForm = -1; everywhere with an InvalidateTraversal() method. This saves you having to put comments in explaining why this cryptic operation is occuring, and will make it much easier to change the behaviour in furture if you see fit to do so.

thx for good tips. I am working on it. Printing was done for my testing and i forgot to remove it. Can you explain that: "Generally, you are opening a serious can of worms when you expose implementation details like your Node class to the world, because anyone can modify a Node from the BST and ruin the data-structure: if you don't need to expose this information, then do not." How can i fix it? — Urban Kravos
– Urban Kravos, Commented Apr 27, 2019 at 21:01
@UrbanKravos if you put Node inside BST and make it private, then suddenly the compiler will complain everywhere you are exposing this detail. Then you just have to go through and 'fix' every spot where Node is escaping (e.g. you'd have to make Insert(Node) private, same with BinarySearch (could expose it instead as a bool Contains(int value) method, which is much nicer than a null check)). Without a detailed spec, it's hard to know whether you need Node to leak or not, but if you don't, you can provide a much tighter API by just using int (or a generic type) everywhere. — VisualMelon
– VisualMelon, Commented Apr 27, 2019 at 21:22

Stack Exchange Network

C# Binary search tree

1 Answer 1

API

Correctness

Error handling

Printing

Naming and Spelling

Don't Repeat Yourself

You must log in to answer this question.

Hot Network Questions

C# Binary search tree

1 Answer 1

API

Correctness

Error handling

Printing

Naming and Spelling

Don't Repeat Yourself

You must log in to answer this question.

Related

Hot Network Questions