Programming

We are given a binary tree (with root node root), a target node, and an integer value K.

Return a list of the values of all nodes that have a distance K from the target node.  The answer can be returned in any order.

 

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

Output: [7,4,1]

Explanation: 
The nodes that are a distance 2 from the target node (with value 5)
have values 7, 4, and 1.

Note that the inputs "root" and "target" are actually TreeNodes.
The descriptions of the inputs above are just serializations of these objects.

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    
    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        buildGraph(null, root);
        
        List<Integer> rst = new LinkedList<>();
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        
        int distance = 0;
        queue.offer(target.val);
        visited.add(target.val);
        
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                int curr = queue.poll();
                if(distance == K) {
                    rst.add(curr);
                }
                
                if(graph.containsKey(curr)) {
                    for(int neigh : graph.get(curr)) {
                        if(visited.contains(neigh)) {
                            continue;
                        }
                        queue.offer(neigh);
                        visited.add(neigh);
                    }
                }
            }
            distance++;
        }
        
        return rst;
    }
    
    private void buildGraph(TreeNode parent, TreeNode child) {
        if(parent != null) {
            graph.computeIfAbsent(parent.val, key -> new LinkedList<>()).add(child.val);
            graph.computeIfAbsent(child.val, key -> new LinkedList<>()).add(parent.val);
        }
        
        if(child.left != null) {
            buildGraph(child, child.left);
        }
        
        if(child.right != null) {
            buildGraph(child, child.right);
        }
    }
}

Programming Queue

Priority queues are a generalisation of stacks and queues.
Rather than inserting and deleting elements in a fixed order, each element is assigned a priority represented by an integer.
We always remove an element with the highest priority, which is given by the minimal integer priority assigned. Priority queues often have a fixed size.

Advantages of Priority Queues

  • Easy to implement
  • Processes with different priority can be efficiently handled
  • Used in Applications with differing requirements
  • Nodes can be weighted, allowing those with greater precedence to be moved towards the head of the queue, in front of those with lesser priority, rather than always being added to the tail of the queue as would happen in a normal queue
  • O(n) In the worst case, you might have to traverse the entire list when inserting a node based on key in a priority queue
  • A priority queue does not permit null elements

Disadvantages of Priority Queues

  • insertions are no longer performed in constant time as new nodes must use insertion sort to find their place in the queue (behind nodes with greater or equal priority). However, if the variable weights are finite, maintaining pointers for each weight in a static array will provide constant time insertions.

Implementation of Priority Queues

Priority queue can be implemented using an array, a list, a binary search tree or a heap, although the most efficient one being the heap. The Undo operation is achieved using a stack.

Implementations

  • Before we come to heaps, it is worth considering different implementation choices and consider the complexity of various operations.
    The first idea is to use an unordered array of size limit, where we keep
    a current index n. Inserting into such an array is a constant-time operation, since we only have to insert it at n and increment n. However, finding the minimum will take O(n), since we have to scan the whole portion of the array that’s in use. Consequently, deleting the minimal element also takes (n): first we find the minimal element, then we swap it with the last element in the array, and decrement n
  • keep the array sorted. In this case, inserting an element is O(n). We can quickly (in O(log(n)) steps) find the place i where it belongs using binary search, but then we need to shift elements to make room for the insertion. This take O(n) copy operations. Finding the minimum is O(1) (since it is stored at index 0 in the array). We can also make deleting it O(1) if we keep the array sorted in descending order, or if we keep two array indices: one for the smallest current element and one for the largest.
  • heaps will have logarithmic time for insert and deleting the minimal element

Usually, the number of inserts and deletes to roughly balance. So, neither the unordered nor the ordered array provide a good data structure since a sequence of n inserts and deletes will have worst-case complexity O(n2).

The idea of the heap is to use something cleverly situated in between. A min-heap is like an array that is ordered to some extent: enough, that the least element can be found in O(1), but not so rigidly that inserting would take O(n) time. A min-heap is a binary tree where the invariant guarantees that the least element is at the root. For this to be the case we just require that the key of a node is less or equal to the keys of its children. So, each node except the root is greater or equal to its parent.

The elements of the priority queue are ordered according to the natural ordering, or by a Comparator provided at queue construction time

Breadth First Search BFS Queue Tree

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

Note:

  1. The range of node’s value is in the range of 32-bit signed integer.

Solution (Runtime: 6 ms)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> rst = new ArrayList<>();
        
        if(root == null) {
            return rst;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while(!queue.isEmpty()) {
            int size = queue.size();
            double sum = 0;
            
            for(int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                
                sum += curr.val;
                
                if(curr.left != null) {
                    queue.offer(curr.left);
                }
                
                if(curr.right != null) {
                    queue.offer(curr.right);
                }
            }
            
            rst.add(sum / size);
        }
        
        return rst;
    }
}

Binary Search Programming Tree

Binary Search Trees or BST is an ordered binary tree where all the nodes on the left of a node are less or equal to the node’s own value and all the values on the right are greater or equal to the node’s own value.

A Binary Tree is a tree with only two children, left and right.

Advantages of BST

  • lookup operation (locating a particular node in the tree) is fast and simple
    • Time: O(log(n)) for a balanced binary search tree
    • Worst case is O(n) where each node has only one child and it becomes a linked list
    • usually it happens
  • Insert/Delete are also O(log(n)) time in BSTs
  • you can obtain the smallest element by following all the left children and the largest element by following all the right children
  • Nodes can be printed in order in O(n) time
  • Given a node, you can even find the next highest node in O(log(n)) time.

Programming

In Breadth-first search (BFS) you start with the root, move left to right across the second level, then move left to right across the third level, and so forth. Breadth-first search (BFS) is a method for exploring a tree or graph. In a BFS, you first explore all the nodes one step away, then all the nodes two steps away, etc.

A BFS uses additional memory because it is necessary to track the child nodes for all nodes on a given level while searching that level.

Remember to use Queue, and isVisited flag to avoid infinite loop

Complexity
Time complexity: O(n)
Space complexity: best: O(1), worst: O(n/2)=O(n)

Advantages:
* A BFS will find the shortest path between the starting point and any other reachable node. A depth-first search will not necessarily find the shortest path.

Disadvantages
* A BFS on a binary tree generally requires more memory than a DFS.

Depth First Search DFS Graphs Java Programming

If we are given a binary tree (with the root node), we can build a tree map without generating extra edges by using this helper method:

  • it is an undirected graph with no weight/weight value of 1
  • the method of drawing is done using Depth First Search – DFS
Map<TreeNode, List<TreeNode>> graph = new HashMap<>();

buildTreeGraph(null, root);

private void buildTreeGraph(TreeNode parent, TreeNode child) {
    if (parent != null) {
        graph.computeIfAbsent(parent, x -> new ArrayList<>()).add(child);
        graph.computeIfAbsent(child, x -> new ArrayList<>()).add(parent);
    }

    if (child.left != null) {
        buildTreeGraph(child, child.left);
    }
    if (child.right != null) {
        buildTreeGraph(child, child.right);
    }
}

Notes:

  1. The method Map.computeIfAbsent(key, Function) computes the new value and associates it with the key if there is no mapping for the given key or the mapping is null.
    Also, it returns the new value associated with the key. If the mapping function will return null the value will not be put into the map.
  2. The TreeNode class is displayed below:
 public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
 }