CODEWITHSUNDEEP
c#binary-search-tree
Bartolinio Kooperinio
Bartolinio Kooperinio

Reputation: 49

Mapping binary search tree

I have this binary search tree with Node class and I need to write mapping and filtering method for it but I have no clue how can I go through the whole tree. My every attempt to go through it skipped almost half of the tree.

public class BST<T> where T:IComparable<T>
{
    public class Node
    {
       public T value { get; }
       public Node left;
       public Node right;

        public Node(T element)
        {
            this.value = element;
            left = null;
            right = null;
        }
    }
    private Node root;
    private void add(T element)
    {
        if (root == null)
            root = new Node(element);
        else
        {
            add(element, root);
        }
    }
    public void add(T element, Node leaf)
    {
        if(element.CompareTo(leaf.value) > 0)
        {
            if (leaf.right == null)
                leaf.right = new Node(element);
            else
                add(element,leaf.right);
        }
        else
        {
            if (leaf.left == null)
                leaf.left = new Node(element);
            else
                add(element, leaf.left);
        }
    }
}

Upvotes: 0

Views: 229

Answers (1)

trincot
trincot

Reputation: 351318

I have no clue how can I go through the whole tree

There are many ways to do that. One is to make your class iterable.

For that you can define the following method on your Node class:

    public IEnumerator<T> GetEnumerator()
    {
        if (left != null) {
            foreach (var node in left) {
                yield return node;
            }
        }
        yield return value;
        if (right != null) {
            foreach (var node in right) {
                yield return node;
            }
        }
    }

And delegate to it from a similar method on your BST class:

public IEnumerator<T> GetEnumerator()
{
    if (root != null) {
        foreach (var node in root) {
            yield return node;
        }
    }
}

Now you can write code like this:

    var tree = new BST<int>();
    tree.add(4);
    tree.add(2);
    tree.add(3);
    tree.add(6);
    tree.add(5);
    
    foreach (var value in tree) {
        Console.WriteLine(value);
    }

I need to write mapping and filtering method for it

It depends on what you want the result of a mapping/filtering function to be. If it is just a sequence of values, the above should be simple to adapt. If a new tree should be created with the mapped/filtered values, then feed these values back into a new tree (calling its add), or (in case of mapping) use the same recursive pattern of the above methods to create a new method that does not do yield, but creates a new tree while iterating the existing nodes, so the new tree has the same shape, but with mapped values.

Upvotes: 1

Related Questions