# Question

Formatted question description: https://leetcode.ca/all/94.html

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]


Example 2:

Input: root = []
Output: []


Example 3:

Input: root = [1]
Output: [1]


Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

# Algorithm

### Using stack

The iterative solution using the stack is also one of the solutions that meet the requirements of this question. It needs to be done with a stack.

The idea is to start from the root node, first push the root node into the stack, and then push all its left child nodes into the stack, then take out the top node of the stack, save the node value, and then move the current pointer to its right child node. If there is a right child node, all the left child nodes can be pushed onto the stack in the next cycle. This ensures that the access sequence is left-root-right.

### No stack

Neither recursion nor stack can be used, so how to ensure that the access sequence is the left-root-right of the in-order traversal. It turns out that a binary tree of clues needs to be constructed, and all the empty right child nodes need to be pointed to the next node traversed by the in-order, so that after the in-order traverses the left child node, it can smoothly return to its root node and continue the traversal.

The specific algorithm is as follows:

1. Initialize the pointer cur to point to root

2. When cur is not empty

• if cur has no left child node
• a) Print out the value of cur
• b) Point the cur pointer to its right child node
• on the contrary, cur has left child node. Point the pre pointer to the rightmost child node in the left subtree of cur
• If pre does not have a right child node
• a) Point its right child node back to cur
• b) cur points to its left child node
• on the contrary
• a) Empty the right child node of pre
• b) Print the value of cur
• c) Point the cur pointer to its right child node

# Code

• import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Stack;

public class Binary_Tree_Inorder_Traversal {

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/

public class Solution_optmize {
public List<Integer> inorderTraversal(TreeNode root) {

List<Integer> list = new ArrayList<Integer>();
if (root == null) {
return list;
}

Stack<TreeNode> sk = new Stack<>();
TreeNode current = root;

while (!sk.isEmpty() || current != null) {

while (current != null) {
sk.push(current);
current = current.left;
} // @note: 一逼撸到最左边

// @note: 没有push left的操作，就不会无限循环，也不需要mark是否visited
TreeNode leftOrMiddle = sk.pop();

current = leftOrMiddle.right; // if right is null here, next time pop parent node
}

return list;
}
}

class Solution_noStack { // but modifying original tree
public List<Integer> inorderTraversal(TreeNode root) {

List<Integer> result = new ArrayList<>();
TreeNode current = root;
TreeNode prev;

while (current != null) {
if (current.left == null) {

// only handle right child
current = current.right; // move to next right node
} else { // has a left subtree
prev = current.left;
while (prev.right != null) { // find rightmost
prev = prev.right;
}
prev.right = current; // put cur after the pre node
TreeNode temp = current; // store cur node
current = current.left; // move cur to the top of the new tree
temp.left = null; // original cur left be null, avoid infinite loops
}
}

return result;
}
}

public class Solution {

List<Integer> list = new ArrayList<Integer>();

public List<Integer> inorderTraversal(TreeNode root) {

// mark if a node is visited already: true is visited. or, just use a Set
HashSet<TreeNode> hs = new HashSet<>();

Stack<TreeNode> sk = new Stack<>();
sk.push(root);

while (!sk.isEmpty()) {

TreeNode current = sk.pop();

if (current == null) {
continue;
}

// @note: careful to check left visited, or else infinite looping
if (current.left != null && !hs.contains(current.left)) {
sk.push(current);
sk.push(current.left);

} else {

if (current.right != null && !hs.contains(current.right)) {
sk.push(current.right);
}

}
}

return list;
}
}

class Solution_recursion {

List<Integer> result = new ArrayList<>();

public List<Integer> inorderTraversal(TreeNode root) {
dfs(root);
return result;
}

public void dfs(TreeNode root) {
if (root == null) {
return;
}

dfs(root.left);
dfs(root.right);
}
}
}

############

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
while (root != null) {
if (root.left == null) {
root = root.right;
} else {
TreeNode prev = root.left;
while (prev.right != null && prev.right != root) {
prev = prev.right;
}
if (prev.right == null) {
prev.right = root;
root = root.left;
} else {
prev.right = null;
root = root.right;
}
}
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/binary-tree-inorder-traversal/
// Time: O(N)
// Space: O(H)
class Solution {
private:
vector<int> ans;
void dfs(TreeNode* root) {
if (!root) return;
dfs(root->left);
ans.push_back(root->val);
dfs(root->right);
}
public:
vector<int> inorderTraversal(TreeNode* root) {
dfs(root);
return ans;
}
};

• # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
stack = []
current = root
res = []
while stack or current:
while current:
stack.append(current)
current = current.left
left_or_middle = stack.pop()
res.append(left_or_middle.val)
current = left_or_middle.right
return res

# no stack, but modifying original tree
class Solution:
def inorderTraversal(self, root):
result = []
current = root
prev = None

while current:
if current.left is None:
result.append(current.val)
current = current.right
else:
prev = current.left
while prev.right:
prev = prev.right
prev.right = current
temp = current
current = current.left
temp.left = None

return result

class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
while root:
if root.left is None:
ans.append(root.val)
root = root.right
else:
prev = root.left
while prev.right and prev.right != root:
prev = prev.right
if prev.right is None:
prev.right = root
root = root.left
else:
ans.append(root.val)
prev.right = None
root = root.right
return ans

###########

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

'''
>>> stack = [(1, None)]
>>> stack.extend([(0, None), (2, "b"), (3, "c")])
>>> stack
[(1, None), (0, None), (2, 'b'), (3, 'c')]
'''
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""

# stack to hold tuple (), '0' meaning a parent node for current level, '1' meaning a child node
res, stack = [], [(1, root)]
while stack:
p = stack.pop()
if not p[1]: continue
stack.extend([(1, p[1].right), (0, p[1]), (1, p[1].left)]) if p[0] != 0 else res.append(p[1].val)
return res


• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) []int {
var ans []int
for root != nil {
if root.Left == nil {
ans = append(ans, root.Val)
root = root.Right
} else {
prev := root.Left
for prev.Right != nil && prev.Right != root {
prev = prev.Right
}
if prev.Right == nil {
prev.Right = root
root = root.Left
} else {
ans = append(ans, root.Val)
prev.Right = nil
root = root.Right
}
}
}
return ans
}

• /**
* Definition for a binary tree node.
* class TreeNode {
*     val: number
*     left: TreeNode | null
*     right: TreeNode | null
*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.left = (left===undefined ? null : left)
*         this.right = (right===undefined ? null : right)
*     }
* }
*/

function inorderTraversal(root: TreeNode | null): number[] {
if (root == null) {
return [];
}
return [
...inorderTraversal(root.left),
root.val,
...inorderTraversal(root.right),
];
}


• /**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root) {
let ans = [];
while (root) {
if (!root.left) {
ans.push(root.val);
root = root.right;
} else {
let prev = root.left;
while (prev.right && prev.right != root) {
prev = prev.right;
}
if (!prev.right) {
prev.right = root;
root = root.left;
} else {
ans.push(root.val);
prev.right = null;
root = root.right;
}
}
}
return ans;
};


• // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, res: &mut Vec<i32>) {
if root.is_none() {
return;
}
let node = root.as_ref().unwrap().borrow();
Self::dfs(&node.left, res);
res.push(node.val);
Self::dfs(&node.right, res);
}

pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut res = vec![];
Self::dfs(&root, &mut res);
res
}
}