recriating a bst tree from preorder

This is a discussion on recriating a bst tree from preorder within the C Programming forums, part of the General Programming Boards category; i have an array of the pre order traversal and i know that the root it arr[0] and its left ...

  1. #1
    Banned
    Join Date
    Jul 2009
    Posts
    46

    recriating a bst tree from preorder

    i have an array of the pre order traversal
    and i know that the root it arr[0]
    and its left son is arr[1]

    whats the formula for spotting the value of its right son value

    ??

  2. #2
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Given, node with index i and it's left child is 2i. Working out what the right child is shouldn't be too hard for you.

    Hint: Draw the tree and its array.

  3. #3
    Banned
    Join Date
    Jul 2009
    Posts
    46
    its not 2i but i+1

    i got to that conclution too

    but the right son is hard
    because if a tree is not simetric and somewhere we dont have a left of right node
    then we cant break it into two

  4. #4
    Banned
    Join Date
    Jul 2009
    Posts
    46
    i think the answer is searching the first node whoch is larger then arr[i]

    is it ok?

  5. #5
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,758
    Just use a value that wasn't in the tree before you flattened it as nil.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 06:59 PM
  2. BST delete again, but this time I think I'm close
    By tms43 in forum C++ Programming
    Replies: 9
    Last Post: 11-05-2006, 06:24 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21