257.binary-tree-paths.md

257. Binary Tree Paths

Test Cases

Normal Cases

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

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 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: O(n * h) = O(n^2) in worst case
  • Visit all nodes O(n)
  • Concatenate the string every time O(h).
  • In a skewed tree, h = n, so the time complexity is O(n^2) in worst case.
• Space Complexity: O(n * h) = O(n^2) in worst case
  • Recursive stack: O(h)
  • Store O(#leaves) strings result of size O(h) each.
  • In a skewed tree, h = n, so the space complexity is O(n^2) in worst case.

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
}