yokolet's notelets

  1. Trees
  2. Binary Tree Inorder Traversal

Trees

Binary Tree Inorder Traversal

Problem Description

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

Constraints:

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

https://leetcode.com/problems/binary-tree-inorder-traversal/

Examples

Example 1
Input: root = [1,null,2,3]
Output: [1,3,2]
Explanation:
1
 \
  2
 /
3
Example 2
Input: root = []
Output: []
Example 3
Input: root = [1]
Output: [1]

How to Solve

This is a basic inorder traversal problem. Just visit all nodes in the binary tree following the inorder manner.

The tree traversal here takes the depth-first search (DFS) style. The traverse function does the DFS and saves values between going left and right nodes.

Solution

  • #include <vector>
    
    using namespace std;
    
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode() : val(0), left(nullptr), right(nullptr) {}
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
        TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     };
    
    class BinaryTreeInorderTraversal {
    private:
        vector<int> traverse(vector<int> &values, TreeNode *root)
        {
            if (root)
            {
                values = traverse(values, root->left);
                values.push_back(root->val);
                values = traverse(values, root->right);
            }
            return values;
        }
    public:
        vector<int> inorderTraversal(TreeNode* root) {
            vector<int> values;
            return traverse(values, root);
        }
    };
    
  • /**
     * 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 BinaryTreeInorderTraversal {
        private List<Integer> traverse(List<Integer> values, TreeNode root) {
            if (root == null) { return values; }
            traverse(values, root.left);
            values.add(root.val);
            traverse(values, root.right);
            return values;
        }
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> values = new ArrayList<Integer>();
            return traverse(values, root);
        }
    }
    
  • 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) {
      const traverse = function(values, root) {
        if (root === null) { return values; }
        values = traverse(values, root.left);
        values.push(root.val);
        values = traverse(values, root.right);
        return values
      }
      return traverse([], root);
    };
    
    
  • # 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
    
    from typing import Optional
    
    class BinaryTreeInorderTraversal:
        def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
            def traverse(result, root):
                if not root:
                    return result
                result = traverse(result, root.left)
                result.append(root.val)
                result = traverse(result, root.right)
                return result
            return traverse([], root)
    
  • # Definition for a binary tree node.
    # class TreeNode
    #     attr_accessor :val, :left, :right
    #     def initialize(val = 0, left = nil, right = nil)
    #         @val = val
    #         @left = left
    #         @right = right
    #     end
    # end
    # @param {TreeNode} root
    # @return {Integer[]}
    def traverse(values, root)
      if !root
        return values
      end
      traverse(values, root.left)
      values << root.val
      traverse(values, root.right)
      values
    end
    
    def inorder_traversal(root)
      traverse([], root)
    end
    

Complexities

  • Time: O(n)
  • Space: O(n)
Easy
Depth-First Search
Binary Tree