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

1008. Construct Binary Search Tree from Preorder Traversal (Medium)

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

Example 1:

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Note:

1 <= preorder.length <= 100
The values of preorder are distinct.

Related Topics:
Tree

Solution - Stack

We use a stack<pair<TreeNode*, int>> s to keep track of the parent nodes where the first item in the pair is the parent node, and the second item is the right bound of the parent node (i.e. the grandparent’s node value).

If the current node value is smaller than the value of the parent node at the stack top, we should add this new node as the left child of the parent node, and push node, s.top().first->val to the stack top.
Otherwise, we keep popping the stack top until A[i] < s.top().second. Then we add the new node as the right child of the parent node at the stack top, and push node, s.top().second to the stack top.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        int length = preorder.length;
        int[] inorder = new int[length];
        System.arraycopy(preorder, 0, inorder, 0, length);
        Arrays.sort(inorder);
        return buildTree(preorder, inorder);
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0)
            return null;
        TreeNode root = new TreeNode(preorder[0]);
        int length = preorder.length;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return 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 Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        return dfs(preorder, 0, preorder.length - 1);
    }

    private TreeNode dfs(int[] preorder, int i, int j) {
        if (i > j || i >= preorder.length) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[i]);
        int left = i + 1, right = j + 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (preorder[mid] > preorder[i]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        root.left = dfs(preorder, i + 1, left - 1);
        root.right = dfs(preorder, left, j);
        return root;
    }
}

// OJ: https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/
// Time: O(N^2)
// Space: O(H)
class Solution {
private:
    TreeNode* construct(vector<int> &preorder, int begin, int end) {
        if (begin >= end) return NULL;
        auto root = new TreeNode(preorder[begin]);
        int i = begin + 1;
        while (i < end && preorder[i] < preorder[begin]) ++i;
        root->left = construct(preorder, begin + 1, i);
        root->right = construct(preorder, i, end);
        return root;
    }
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        return construct(preorder, 0, preorder.size());
    }
};

// OJ: https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/
// Time: O(N)
// Space: O(H)
class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& A) {
        stack<pair<TreeNode*, int>> s;
        s.emplace(new TreeNode(A[0]), INT_MAX);
        auto root = s.top().first;
        for (int i = 1; i < A.size(); ++i) { 
            auto node = new TreeNode(A[i]);
            if (A[i] < s.top().first->val) {
                s.top().first->left = node;
                s.emplace(node, s.top().first->val);
            } else {
                while (A[i] > s.top().second) s.pop();
                s.top().first->right = node;
                s.emplace(node, s.top().second);
            }
        }
        return 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
class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        def dfs(preorder):
            if not preorder:
                return None
            root = TreeNode(preorder[0])
            left, right = 1, len(preorder)
            while left < right:
                mid = (left + right) >> 1
                if preorder[mid] > preorder[0]:
                    right = mid
                else:
                    left = mid + 1
            root.left = dfs(preorder[1:left])
            root.right = dfs(preorder[left:])
            return root

        return dfs(preorder)

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

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

class Solution(object):
    def bstFromPreorder(self, preorder):
        """
        :type preorder: List[int]
        :rtype: TreeNode
        """
        if not preorder: return None
        root = TreeNode(preorder[0])
        N = len(preorder)
        i = 1
        while i < N:
            if preorder[i] > preorder[0]:
                break
            i += 1
        root.left = self.bstFromPreorder(preorder[1:i])
        root.right = self.bstFromPreorder(preorder[i:])
        return root

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func bstFromPreorder(preorder []int) *TreeNode {
	var dfs func(i, j int) *TreeNode
	dfs = func(i, j int) *TreeNode {
		if i > j || i >= len(preorder) {
			return nil
		}
		root := &TreeNode{Val: preorder[i]}
		left, right := i+1, len(preorder)
		for left < right {
			mid := (left + right) >> 1
			if preorder[mid] > preorder[i] {
				right = mid
			} else {
				left = mid + 1
			}
		}
		root.Left = dfs(i+1, left-1)
		root.Right = dfs(left, j)
		return root
	}
	return dfs(0, len(preorder)-1)
}

/**
 * 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 bstFromPreorder(preorder: number[]): TreeNode | null {
    const n = preorder.length;
    const next = new Array(n);
    const stack = [];
    for (let i = n - 1; i >= 0; i--) {
        while (
            stack.length !== 0 &&
            preorder[stack[stack.length - 1]] < preorder[i]
        ) {
            stack.pop();
        }
        next[i] = stack[stack.length - 1] ?? n;
        stack.push(i);
    }

    const dfs = (left: number, right: number) => {
        if (left >= right) {
            return null;
        }
        return new TreeNode(
            preorder[left],
            dfs(left + 1, next[left]),
            dfs(next[left], right),
        );
    };
    return dfs(0, n);
}

// 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(
        preorder: &Vec<i32>,
        next: &Vec<usize>,
        left: usize,
        right: usize,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if left >= right {
            return None;
        }
        Some(Rc::new(RefCell::new(TreeNode {
            val: preorder[left],
            left: Self::dfs(preorder, next, left + 1, next[left]),
            right: Self::dfs(preorder, next, next[left], right),
        })))
    }

    pub fn bst_from_preorder(preorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        let n = preorder.len();
        let mut stack = Vec::new();
        let mut next = vec![n; n];
        for i in (0..n).rev() {
            while !stack.is_empty() && preorder[*stack.last().unwrap()] < preorder[i] {
                stack.pop();
            }
            if !stack.is_empty() {
                next[i] = *stack.last().unwrap();
            }
            stack.push(i);
        }
        Self::dfs(&preorder, &next, 0, n)
    }
}

1008 - Construct Binary Search Tree from Preorder Traversal

1008. Construct Binary Search Tree from Preorder Traversal (Medium)

Solution - Stack

All Problems

All Solutions

Welcome to Subscribe On Youtube

1008. Construct Binary Search Tree from Preorder Traversal (Medium)

Solution - Stack

All Problems

All Solutions