I am working on Trees and wanted to print out the tree in a Stack

Here's what I got so far.

class TreeNode<T>(var key: T,){
    var left: TreeNode<T>? = null
    var right: TreeNode<T>? = null
}

fun depthFirstValues(root: TreeNode<Char>){
    val stack = mutableListOf(root)
    while (stack.size > 0){
       val current = stack.removeFirst()
//        println(current.key)

        if(current.right!!.equals(true)) stack.add(current.right!!)
        if (current.left!!.equals(true)) stack.add(current.left!!)


    }
    println(stack)
}

fun buildTree(): TreeNode<Char>{
    val a = TreeNode('a')
    val b = TreeNode('b')
    val c = TreeNode('c')
    val d = TreeNode('d')
    val e = TreeNode('e')
    val f = TreeNode('f')


    a.left = b
    a.right = c
    b.left = d
    b.right = e
    c.right = f

    return a
}

I got an emptyList as the return value. I have been tinkering with it throughout the day, but not sure how to get it to work. Any help will be appreciated. Thank you.

CodePudding user response：

I see three major problems with your code.

• You need an extra collection to store the results of the depth-first traversal, if you want to store the entire traversal in a collection, and print it out at the end.

  You can't just use the same stack as the one you use to implement the traversal, because that stack is guaranteed to be empty at the end of the algorithm, as indicated by the condition on the while loop - stack.size == 0.

• You are not actually using stack like a stack. You are removing elements from its front (removeFirst), but adding to its end (add), like a queue. To use it like a stack, you should add to/remove from the same end of the list.

• You are not checking nulls correctly. current.right!!.equals(true) is false if current.right is not null, and will throw an exception if it is null - doesn't make much sense at all, does it?

Fixing these issues, we have:

fun depthFirstValues(root: TreeNode<Char>){
    val stack = mutableListOf(root)
    val result = mutableListOf<Char>()
    while (stack.isNotEmpty()){
        val current = stack.removeLast()
        current.left?.apply(stack::add)
        current.right?.apply(stack::add)
        result.add(current.key) // could also get rid of "result" and just println(current.key) here
    }
    println(result)
}

When applied to your tree, it prints [a, c, f, b, e, d].