Posts

Non-Recursive Tree Navigation

-
Image
In this problem you need to find all elements at a given level in a BST. I realized that unfortunately my solution doesn't take into account the BST property, hence in order to make it slightly faster (as a compromise), I decided to navigate the tree using a Stack. Runs in NLogN which still makes the cut. Code is down below, cheers, ACC. Median of a Binary Search Tree Level - LeetCode You are given the  root  of a  Binary Search Tree (BST)  and an integer  level . The root node is at level 0. Each level represents the distance from the root. Return the  median value  of all node values present at the given  level . If the level does not exist or contains no nodes, return -1. The  median  is defined as the middle element after sorting the values at that level in  non-decreasing  order. If the number of values at that level is even, return the  upper  median (the larger of the two middle elements after sorting).   ...
Post a Comment
Read more

This is a Graph Problem - Not a Tree Problem! Part III

-
Image
Well it can be seen as a tree problem too, but it becomes easier if you use graph notions. First building the graph from the edges, and then performing a BFS to find the distance from {x,y,z} to each node. Ran into TLE quite a bit hence had to limit the use of Hashtable (still using it, but less) in order to make the cut (barely). Code is down below, cheers, ACC. Pythagorean Distance Nodes in a Tree - LeetCode You are given an integer  n  and an undirected tree with  n  nodes numbered from 0 to  n - 1 . The tree is represented by a 2D array  edges  of length  n - 1 , where  edges[i] = [u i , v i ]  indicates an undirected edge between  u i  and  v i . You are also given three  distinct  target nodes  x ,  y , and  z . For any node  u  in the tree: Let  dx  be the distance from  u  to node  x Let  dy  be the distance from  u  to node  y Let...
Post a Comment
Read more