CODEWITHSUNDEEP
c#algorithmbinary-tree
user1108948
user1108948

Reputation:

Printing a binary tree in order

I have a problem to convert a sorted array to a binary tree. I think that I have done it. Now I just want to print all items after conversion to double check it.

My question is that my printing part doesn't print all items. Something is wrong in the method 'inOrderTraversalHelper'.

class Program
{
    // Given an array where elements are sorted in ascending order, 
    // convert it to a height balanced BST
    static int[] arr = new int[8] {1,2,3,4,5,6,7,8};
    static TreeNode node { get; set; }
    static void Main(string[] args)
    {
         node = SortedArrayToBST(arr, 0, arr.Length-1);
         inOrderTraversal();
    }

    static void inOrderTraversal()
    {
        inOrderTraversalHelper(node);
    }
    static void inOrderTraversalHelper(TreeNode r)
    {
        if (r != null)
        {    
          **// UPDATED**

            inOrderTraversalHelper(r.leftNode);
             Console.Write("{0}   ", r.data);
            inOrderTraversalHelper(r.rightNode);
        }
    }
    static TreeNode SortedArrayToBST(int[] a,int start,int end)
    {
        if (start > end) return null;
        int mid = (start + end) / 2;
        TreeNode node = new TreeNode(a[mid]);
        node.leftNode= SortedArrayToBST(a, start, mid-1);
        node.rightNode = SortedArrayToBST(a, mid + 1, end);
        return node;
    }
}

public class TreeNode
{
    public int data;
    public TreeNode leftNode;
    public TreeNode rightNode;

    public TreeNode(int data)
    {
        this.data = data;
    }
}

Upvotes: 0

Views: 1475

Answers (2)

justin.m.chase
justin.m.chase

Reputation: 13665

It's because you are storing the value of the index mid not the value at the index of mid:

int mid = (start + end) / 2;
TreeNode node = new TreeNode(mid);

You are calculating the value of mid and then passing it in as the data. Instead mid should be the index of the value you want. For, example if you had a data set where the data was ordered but non sequential you'd get even stranger results:

{-1,22,33,44,55,66,77,100}

So your code should probably look up the value at index mid instead:

var mid = (int)((start + end) / 2.0);
var node = new TreeNode(arr[mid]);

Upvotes: 1

Bernhard Barker
Bernhard Barker

Reputation: 55609

In SortedArrayToBST, you work with the index mid, rather than with the element a[mid], change:

TreeNode node = new TreeNode(mid);

to:

TreeNode node = new TreeNode(a[mid]);

In the call to the SortedArrayToBST function, you need to pass array size - 1, since the end condition in inclusive, change:

node = SortedArrayToBST(arr, 0, arr.Length);

to:

node = SortedArrayToBST(arr, 0, arr.Length-1);

Also, your inOrderTraversalHelper function isn't actually in-order, but rather post-order.

Upvotes: 0

Related Questions