A Binary Search Tree is a special form of a binary tree. The value in each node must be greater than (or equal to) any values in its left subtree but less than (or equal to) any values in its right subtree.
A binary search tree (BST), a special form of a binary tree, satisfies the binary search property:
Like a normal binary tree, we can traverse a BST in preorder, inorder, postorder or level-order. However, it is noteworthy that inorder traversal in BST will be in ascending order. Therefore, the inorder traversal is the most frequent used traversal method of a BST.
O(N*min(L,H))O(H)preorder traversal: visit the node, go left, then go right.
dfs recursive function
- pass in the head and root
- if root is null, return false
- if head’s value is equal to root.val and bfs result is true, return true
- otherwise, we traverse root.left and root.right with the dfs method.
bfs
- Define a queue and add the root
- Move our listNode forward, since we already found the head
- check if the current value is the curr list node.
- return if curr is null;
class Solution {
public boolean isSubPath(ListNode head, TreeNode root) {
return dfs(head, root);
}
public boolean dfs(ListNode head, TreeNode root){
if (root == null){
return false;
}
if (head.val == root.val && bfs(head,root)){
return true;
}
return dfs(head, root.left) || dfs(head,root.right);
}
public boolean bfs(ListNode head, TreeNode root){
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
ListNode curr = head.next;
while (queue.isEmpty() == false && curr != null){
int size = queue.size();
for(int i = 0; i < size; i ++){
TreeNode node = queue.poll();
if (node.left != null && node.left.val == curr.val){
queue.add(node.left);
}
if (node.right != null && node.right.val == curr.val){
queue.add(node.right);
}
}
if (!queue.isEmpty()){
curr = curr.next;
}
}
return curr == null;
}
}
go down in a binary tree, to see if all the nodes matches the linkedlist if head == null, means we found all the nodes, return true
class Solution {
public boolean isSubPath(ListNode head, TreeNode root) {
return dfs(head,root);
}
private boolean dfs(ListNode head, TreeNode root){
if (root == null){
return false;
}
if (head.val == root.val && matches(head, root) == true){
return true;
}
return dfs(head, root.left) || dfs(head, root.right);
}
//go down in a binary tree, to see if all the nodes matches the linkedlist
//if head == null, means we found all the nodes, return true
private boolean matches(ListNode head, TreeNode root){
if (head == null) { //we found all the nodes inn the linkedlist
return true;
}
if (root == null || head.val != root.val){
return false;
}
return matches(head.next, root.right) || matches(head.next,root.left);
}
}
Queue, store treenodes [ 4 , 5 , 6 ] res = [ 1, 3 , 6 ] size = 3， how many times we need to pull from the queue in order to perform our level order traversal i = 0, iterate from 0 to size-1, a loop telling us that we need to pull from our queue that many times i == size - 1, this is how we know we have the rightmost node from that level
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (queue.isEmpty() == false){
int size = queue.size();
for(int i = 0; i < size; i ++){
TreeNode node = queue.poll();
if (i == size-1){
result.add(node.val);
}
if (node.left != null){
queue.add(node.left);
}
if (node.right != null){
queue.add(node.right);
}
}
}
return result;
}
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ans = new ArrayList<>();
getRightRecur(root, ans, 0);
return ans;
}
private void getRightRecur(TreeNode root, List<Integer> ans, int currDepth){
if (root == null){
return;
}
if (currDepth == ans.size()){
ans.add(root.val);
}
getRightRecur(root.right, ans, currDepth + 1);
getRightRecur(root.left, ans, currDepth + 1);
}
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
int sum = 0;
if(root.left != null ){ //check if it's a leaf.
if (isLeaf(root.left)){
sum += root.left.val;
}else{ //not a leaf, iterate on the left child.
sum += sumOfLeftLeaves(root.left);
}
}
//iterate on the right child to proceed to above process
sum += sumOfLeftLeaves(root.right);
return sum;
}
private boolean isLeaf(TreeNode node){
if (node.left == null && node.right == null){
return true;
}
return false;
}
or,
public int sumOfLeftLeaves(TreeNode root) {
if (root == null){
return 0;
}else if (root.left != null && root.left.left == null && root.left.right == null){
return root.left.val + sumOfLeftLeaves(root.right);
}else{
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}
}
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
int sum = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
//add to the queue if it's not the left child
TreeNode node = queue.poll();
if (node.left != null){//check if it's a leafnode.
if (isLeaf(node.left)){
sum += node.left.val;
}else{
queue.add(node.left);
}
}
if (node.right != null) queue.add(node.right);
}
return sum;
}
private boolean isLeaf(TreeNode node){
return (node.left == null && node.right == null);
}
/**
* 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;
* }
* }
duplicates are not allowed
left < root
right > root
traverse all the way to the left side, the smallest value node in the entire tree
pushing values onto the stack.
fill up the stack, pop stack values off, keep referecnign more and more parent nodes to make sure the orders are in place
stack : 4 2 1
*/
class Solution {
public boolean isValidBST(TreeNode root) {
//in-order: sorted from left, root, right
if (root == null){
return true;
}
Stack<TreeNode> stack = new Stack();
TreeNode pre = null;
while (! stack.isEmpty() || root != null){
while (root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
if (pre != null && root.val <= pre.val){
return false;
}
pre = root;
root = root.right;
}
return true;
}
}
public boolean isValidBST(TreeNode root) {
return isValid(root, null, null);
}
public boolean isValid(TreeNode root, Integer max, Integer min){
if (root == null){
return true;
}else if (min != null && root.val <= min || max != null && root.val >= max){
return false;
}else{
return isValid(root.left, root.val, min) && isValid(root.right, max, root.val);
}
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null){
return list;
}
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.isEmpty()){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
list.add(root.val);
root = root.right;
}
return list;
}
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
recur(root, res);
return res;
}
public void recur(TreeNode root, List<Integer> res){
if (root != null){
recur(root.left, res);
res.add(root.val);
recur(root.right, res);
}
}
}
O(H + k), where H is a tree height. This complexity is defined by the stack, which contains at least H + k elements, since before starting to pop out one has to go down to a leaf.
O(logN+k) for the balanced tree and O(N + k) for completely unbalanced tree with all the nodes in the left subtree.O(H) to keep the stack, where HH is a tree height.
O(N) in the worst case of the skewed tree, and O(logN) in the average case of the balanced tree. public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
while(root != null || stack.isEmpty() == false){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
if (--k == 0){
break;
}
root = root.right;
}
return root.val;
}
class Solution {
public int kthSmallest(TreeNode root, int k) {
//The idea is to build an inorder traversal of BST which is an array sorted in the ascending order.
//Now the answer is the k - 1th element of this array.
ArrayList<Integer> ans = new ArrayList<>();
inOrder(ans, root);
return ans.get(k-1);
}
//inorder traversal is left, root, right, which would be sorting the nodes in an ascending order
public void inOrder(List<Integer> ans, TreeNode root){
if (root != null){
inOrder(ans, root.left);
ans.add(root.val);
inOrder(ans, root.right);
}
}
}