701. Insert into a Binary Search Tree Medium

1/**
2 * [701] Insert into a Binary Search Tree
3 *
4 * You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
5 * Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/05/insertbst.jpg" style="width: 752px; height: 221px;" />
9 * Input: root = [4,2,7,1,3], val = 5
10 * Output: [4,2,7,1,3,5]
11 * Explanation: Another accepted tree is:
12 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/05/bst.jpg" style="width: 352px; height: 301px;" />
13 * 
14 * Example 2:
15 * 
16 * Input: root = [40,20,60,10,30,50,70], val = 25
17 * Output: [40,20,60,10,30,50,70,null,null,25]
18 * 
19 * Example 3:
20 * 
21 * Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
22 * Output: [4,2,7,1,3,5]
23 * 
24 *  
25 * Constraints:
26 * 
27 * 	The number of nodes in the tree will be in the range [0, 10^4].
28 * 	-10^8 <= Node.val <= 10^8
29 * 	All the values Node.val are unique.
30 * 	-10^8 <= val <= 10^8
31 * 	It's guaranteed that val does not exist in the original BST.
32 * 
33 */
34pub struct Solution {}
35use crate::util::tree::{TreeNode, to_tree};
36
37// problem: https://leetcode.com/problems/insert-into-a-binary-search-tree/
38// discuss: https://leetcode.com/problems/insert-into-a-binary-search-tree/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42// Definition for a binary tree node.
43// #[derive(Debug, PartialEq, Eq)]
44// pub struct TreeNode {
45//   pub val: i32,
46//   pub left: Option<Rc<RefCell<TreeNode>>>,
47//   pub right: Option<Rc<RefCell<TreeNode>>>,
48// }
49// 
50// impl TreeNode {
51//   #[inline]
52//   pub fn new(val: i32) -> Self {
53//     TreeNode {
54//       val,
55//       left: None,
56//       right: None
57//     }
58//   }
59// }
60use std::rc::Rc;
61use std::cell::RefCell;
62impl Solution {
63    pub fn insert_into_bst(root: Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
64        Some(Rc::new(RefCell::new(TreeNode::new(0))))
65    }
66}
67
68// submission codes end
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_701() {
76    }
77}
78