CODEWITHSUNDEEP
algorithmtree
Chris ten Den
Chris ten Den

Reputation: 569

Tree Level-Order Traversal of Elements in a Vector

I am looking for an algorithm to take a list of x values and loop through them starting in the middle then the middle of the left then the middle of the right, then the middle of the middle of the left...like a tree.

I don't think recursion will work because it will traverse down one side completely before getting to the other side. I need to parse through evenly.

Pretend this is a list of 50 numbers:
.................................................. (50)

Need to find the 25th element first

........................1......................... (lvl1)

Then the 12th, then 38th
...........2.........................3............ (lvl2)

Then the 6,18   31,44
.....4...........5.............6...........7...... (lvl3)

Then the 3,9,15,21   28,34,41,48
..8.....9.....a......b.....c.......d.....e.....f.. (lvl4)

etc... until all the values have been traversed. So by the time lvl4 is hit, i've seen 1,2,3,4,5,6,7,8,9,a,b,c,d,e,f in that order.

All my attempts have flopped to do this iteratively.

Efficiency is not critical as it won't be run often.

Hopefully my question is clear. Thank-you

Upvotes: 1

Views: 279

Answers (2)

dfrib
dfrib

Reputation: 73206

(The solution that follows is written in Swift, but I hope you can follow it and translate to your favourite language of choice, in case you wish to make use of it)

We can quite easily come up with a solution that works in the special case where your number of array values describe a full(/proper) binary tree, i.e., if numElements = 2^(lvl-1)+1, where lvl is the level of your tree. See function printFullBinaryTree(...) below.

Now, we can also somewhat with ease expand any array into one that describes a full binary tree, see expandToFullBinary. '

By combining these two methods, we have a general method for input arrays of any size.

Expand any array into one that describes a full binary tree:

/* given 'arr', returns array expanded to full binary tree (if necessary) */
func expandToFullBinary(arr: [String], expandByCharacter: String = "*") -> [String] {

    let binLength = Int(pow(2.0,Double(Int(log2(Double(arr.count)))+1)))-1
    if arr.count == binLength {
        return arr
    }
    else {
        let diffLength = binLength - arr.count
        var arrExpanded = [String](count: binLength, repeatedValue: expandByCharacter)

        var j = 0
        for i in 0 ..< arr.count {
            if i < (arr.count - diffLength) {
                arrExpanded[i] = arr[i]
            }
            else {
                arrExpanded[i+j] = arr[i]
                j = j+1
            }
        }

        return arrExpanded
    }
}

Print array (that describes a full binary tree) as a binary tree according to your question specifications:

/* assumes 'arr' describes a full binary tree */
func printFullBinaryTree(arr: [String]) {

    var posVectorA : [Int] = [arr.count/2]
    var posVectorB : [Int]
    var splitSize : Int = arr.count/2

    var elemCount = 0

    if arr.count < 2 {
        print("\(arr.first ?? "")")
    }
    else {
        while elemCount < arr.count {
            posVectorB = []
            splitSize = splitSize/2
            for i in posVectorA {

                if elemCount == arr.count {
                    print("noo")
                    break
                }

                print(arr[i], terminator: " ")
                elemCount = elemCount + 1

                posVectorB.append(i-splitSize-1)
                posVectorB.append(i+splitSize+1)
            }
            print("")
            posVectorA = posVectorB
        }
    }
}

Example for a vector describing a full binary tree as well as one describing a non-full binary tree:

/* Example */
var arrFullBinary : [String] = ["8", "4", "9", "2", "a", "5", "b", "1", "c", "6", "d", "3", "e", "7", "f"]

var arrNonFullBinary : [String] = ["g", "8", "h", "4", "i", "9", "j", "2", "a", "5", "b", "1", "c", "6", "d", "3", "e", "7", "f"]

printFullBinaryTree(expandToFullBinary(arrFullBinary, expandByCharacter: ""))
/* 1
   2 3
   4 5 6 7
   8 9 a b c d e f    */

printFullBinaryTree(expandToFullBinary(arrNonFullBinary, expandByCharacter: ""))
/* 1
   2 3
   4 5 6 7
   8 9 a b c d e f
   g h i j            */

Upvotes: 0

Ami Tavory
Ami Tavory

Reputation: 76396

You can solve this via a queue data structure and some math.

Start by pushing in the tuple (0, 25, 49). This indicates that this is a node at position 25, splitting the range 0-49. So the queue should look like this:

[(0, 25, 49)]

Now at each point, remove the front of the queue, print the element at the index, and push in the descendants. So, for example, when you pop (0, 25, 49), how to track the descendants? The left descendant is the middle of the range 0-24, so you would push in (0, 12, 24). The right descendant is the middle of the range 26-49, so you would push in (26, 38, 49). So the queue should look like this:

[(0, 13, 23), (26, 38, 49)].

Et cetera.

Upvotes: 1

Related Questions