C# Find Specific Node in Binary Search Tree

Question

been noodling around with BST's and I have a pretty good idea of them but I would like to be able to search for a particular node in the BST and have it tell me if it exists. I am using strings in the BST and everything seems to work well but I cannot figure out this Find method. If someone could tell me what I am doing wrong and how to fix it this would be appreciated.

class Node
    {          
        public string number;
        public string data;
        public Node left;
        public Node right;
        public string Content;
        public Node(string data)
        {
            this.data = data;
        }
    }
    class BinarySearchTree
    { 
        public Node root, current;
        public BinarySearchTree()
        {
            this.root = null;
        }

        public void AddNode(string a) // code to insert nodes to the binary search tree
        {
            Node newNode = new Node(a); //create a new node
            if (root == null) // if the tree is empty new node will be the root node
                root = newNode;
            else
            {
                Node previous;
                current = root;

                while (current != null)
                {
                    previous = current;

                    if (a.CompareTo(current.data) < 1) //if the new node is less than the            current node
                    {
                        current = current.left;
                        if (current == null)
                            previous.left = newNode;
                    }                         
                    else //if the new node is greater than the current node
                    {
                        current = current.right;

                        if (current == null)
                            previous.right = newNode;
                    }
                }
            }
        }

        public string FindNode(Node node, string s)
        {
            if (root == null)
                return Output = "not found";
            else if (s.CompareTo(root.data) < 1)
                return FindNode(root.left, s);
            else if (s.CompareTo(root.data) > 1)
                return FindNode(root.right, s);

            return Output = "found";
        }

        string SearchResult = "";
        static string Output = "";
        public string Display(Node rootNode)
        {
            if (rootNode != null)
            {
                Display(rootNode.left);
                Output += rootNode.data;
                Display(rootNode.right);
            }
            return Output;
        }           
    }

    private void btnExecute_Click(object sender, EventArgs e)
    {
        BinarySearchTree btree = new BinarySearchTree();
        btree.AddNode("D");
        btree.AddNode("B");
        btree.AddNode("F");
        btree.AddNode("E");
        btree.AddNode("A");
        btree.AddNode("G");
        btree.AddNode("C");
        string target;
        txtOutput.Text += "The sorted values of the Binary Search Tree are: \r\n \r\n";
        txtOutput.Text += btree.Display(btree.root);
        txtOutput.Text += btree.FindNode(btree.root, "A");

    }

You know, debuggers make life much easier. That said, FindNode() should have node.left, instead of root.left. Same for right. Also your AddNode fails for insertion of existing nodes. — Nicko Po
– Nicko Po, Commented Nov 25, 2015 at 21:50

FireAlkazar · Accepted Answer · 2015-11-25 22:49:43Z

2

Try to change the following:
1. Use CompareTo method with 0 not 1, so a.CompareTo(current.data) < 1 should be a.CompareTo(current.data) < 0
See documentation IComparable.CompareTo Method
2. As your FindNode is recursive call, change root to node usage

public string FindNode(Node node, string s)
{
    if (node == null)
        return Output = "not found";
    else if (s.CompareTo(node.data) < 0)
        return FindNode(node.left, s);
    else if (s.CompareTo(node.data) > 0)
        return FindNode(node.right, s);

    return Output = "found";
}

Good luck!

answered Nov 25, 2015 at 22:49

FireAlkazar

1,8901 gold badge16 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Shadow Absinthe Over a year ago

This was perfect, found my solution. Thanks

Collectives™ on Stack Overflow

C# Find Specific Node in Binary Search Tree

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related