257.binary-tree-paths.md

257. Binary Tree Paths

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
    1
   / \
  2   3
   \
    5
Output: ["1->2->5", "1->3"] 

Edge / Corner Cases

Input: 
Output: 

Key Ideas to Understand

• When to add value? (node) When we traversal the node.
• When to add arrow? (edge) When the node has left or right child.
• When to backtracking? Depends on when we add the value and arrow, and the data structure we use to store the path.
  • If we use string, we don't need to backtracking.
  • If we use list or similar sequence data structure in collection, we need to remove the last element after the node is visited. (Right after the DFS() of its children)

Backtracking

private val results = mutableListOf<String>()

fun binaryTreePaths(root: TreeNode?): List<String> {
    dfs(root, mutableListOf<String>())
    return results
}

private fun dfs(root: TreeNode?, path: LinkedList<String>) {
    if (root == null) return
    path.addLast("${root.`val`}")
    if (root.left == null && root.right == null) {
        results.add(path.joinToString(""))
        // Remember to backtracking
        path.removeLast()
        return
    }
    if (root.left != null) {
        path.addLast("->")
        dfs(root.left, path)
    }
    if (root.right != null) {
        path.addLast("->")
        dfs(root.right, path)
    }
    path.removeLast()
}

Or to write case by case, it's more clear but more lengthy:

private val results = mutableListOf<String>()

fun binaryTreePaths(root: TreeNode?): List<String> {
    dfs(root, LinkedList<String>())
    return results
}

private fun dfs(root: TreeNode?, path: LinkedList<String>) {
    // Empty
    if (root == null) return

    // Single node or leaf
    if (root.left == null && root.right == null) {
        path.addLast(root.`val`.toString())
        results.add(path.joinToString(""))
        path.removeLast()
        return
    }

    // Node has children (left only or right only or both)
    if (root.left != null) {
        path.addLast(root.`val`.toString())    
        path.addLast("->")
        dfs(root.left, path)
        path.removeLast() // Backtracking arrow
        path.removeLast() // Backtracking value
    }
    if (root.right != null) {
        path.addLast(root.`val`.toString())
        path.addLast("->")
        dfs(root.right, path)
        path.removeLast()
    }
    path.removeLast()
}

Or we can use different to add arrow and value, we can add root first, then add (arrow + value) for children if they exist:

private val results = mutableListOf<String>()
    
fun binaryTreePaths(root: TreeNode?): List<String> {
    if (root == null) return results
    val path = LinkedList<String>()
    // We add root here
    path.add(root.`val`.toString())
    dfs(root, path)
    return results
}

private fun dfs(root: TreeNode?, path: LinkedList<String>) {
    if (root == null) return

    if (root.left == null && root.right == null) {
        results.add(path.joinToString(""))
        // We don't need to backtracking here
        return
    }

    if (root.left != null) {
        // Then add child and backtracking
        path.addLast("->${root.left.`val`}")
        dfs(root.left, path)
        path.removeLast()
    }
    if (root.right != null) {
        path.addLast("->${root.right.`val`}")
        dfs(root.right, path)
        path.removeLast()
    }
}

Recursive with String

private val arrow = "->"
fun binaryTreePaths(root: TreeNode?): List<String> {
    if (root == null) return emptyList()
    val results = mutableListOf<String>()
    dfs(root, "", results)
    return results
}

// Here we use string to store the path, we don't need to backtracking.
private fun dfs(root: TreeNode, str: String, results: MutableList<String>) {
    val s = str + "${root.`val`}"
    // When we reach the leaf node, we add the path to results and return.
    if (root.left == null && root.right == null) {
        results.add(s)
        return
    }
    if (root.left != null) {
        dfs(root.left, s + arrow, results)
    }
    if (root.right != null) {
        dfs(root.right, s + arrow, results)
    }
}

• Time Complexity: We visit all nodes O(n), but we concatenate the string every time, it takes O(n), so the total time takes O(n^2).
• Space Complexity: We store O(n) strings result, and use O(n) for stack, it takes O(n^2).

Iterative with String

fun binaryTreePaths(root: TreeNode?): List<String> {
    val results = mutableListOf<String>()
    if (root == null) return results
    // Node with its string result, we also can use Queue.
    val stack = Stack<Pair<TreeNode, String>>()
    stack.push(root to "")
    while (stack.isNotEmpty()) {
        val pair = stack.pop()
        val node = pair.first
        val str = pair.second + "${node.`val`}"
        
        if (node.left == null && node.right == null) {
            results.add(str)
            continue
        } 
        if (node.left != null) {
            stack.push(node.left!! to str + "->")
        } 
        if (node.right != null) {
            stack.push(node.right!! to str + "->")
        }
    }
    return results
}