Binary Tree Question

Discussion in 'School Work Help' started by ThatGuy, Mar 8, 2012.

  1. ThatGuy

    ThatGuy Well-Known Member

    186
    16
    0
    I'm working on binary search trees for CS class, does anyone know a good way of recursively putting all the nodes into a list?
    The way i'm doing it right now works, but it produces a list with nested lists inside it.
    However, given the operations i can use on the list, i'm not sure if i can flatten it.
     
  2. TutorIndia

    TutorIndia New Member

    3
    1
    0
  3. TutorIndia

    TutorIndia New Member

    3
    1
    0
    /*
    For the key values 1...numKeys, how many structurally unique
    binary search trees are possible that store those keys.

    Strategy: consider that each value could be the root.
    Recursively find the size of the left and right subtrees.
    */
    int countTrees(int numKeys) {

    if (numKeys <=1) {
    return(1);
    }
    else {
    // there will be one value at the root, with whatever remains
    // on the left and right each forming their own subtrees.
    // Iterate through all the values that could be the root...
    int sum = 0;
    int left, right, root;

    for (root=1; root<=numKeys; root++) {
    left = countTrees(root - 1);
    right = countTrees(numKeys - root);

    // number of possible trees with this root == left*right
    sum += left*right;
    }

    return(sum);
    }
    }
     
    #3 TutorIndia, Mar 13, 2013
    Last edited: Mar 13, 2013