Tag: binary search tree

LeetCode 235. Lowest Common Ancestor of a Binary Tree in Java

In this post we will solve LeetCode 235. Lowest Common Ancestor of a Binary Tree problem using Java.

Given a binary search tree (BST), 
find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: 
“The lowest common ancestor is defined between two nodes p and q 
as the lowest node in T that has both p and q as descendants 
(where we allow a node to be a descendant of itself).”

Constraints:

o The number of nodes in the tree is in the range [2, 10^5].
o -10^9 <= Node.val <= 10^9
o All Node.val are unique.
o p != q
o p and q will exist in the BST.

Realated Topics:

o Tree
o Depth-First Search
o Binary Search Tree
o Binary Trea

We are given a Binary Search Tree (BST) and the pointers / references to two nodes in the tree. We need to return the Lowest Common Ancestor (LCA) node. Continue reading “LeetCode 235. Lowest Common Ancestor of a Binary Tree in Java”

LeetCode 669. Trim a Binary Search Tree in Java

In this post we will solve the LeetCode 669 Trim a Binary Search Tree problem. This problem is ranked a Medium by LeetCode. It took me some extra time to figure out what I had to do.

Given the root of a binary search tree and the lowest and highest boundaries as low and high, 
trim the tree so that all its elements lies in [low, high]. 
Trimming the tree should not change the relative structure of the elements that will remain in the tree 
(i.e., any node's descendant should remain a descendant).
It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. 
Note that the root may change depending on the given bounds.

Constraints:

o The number of nodes in the tree in the range [1, 10^4].
o 0 <= Node.val <= 10^4
o The value of each node in the tree is unique.
o root is guaranteed to be a valid binary search tree.
o 0 <= low <= high <= 10^4

Related Topics:

o Tree
o Depth-First Search
o Binary Search Tree
o Binary Tree

The problem clearly states that we are presented with a binary search tree which specifies the relationship between node values. Continue reading “LeetCode 669. Trim a Binary Search Tree in Java”

All Elements in Two Binary Search Trees

The temperature in the Twin Cities of Minneapolis and St. Paul continues to oscillate between negative and positive values in the Fahrenheit scale. The good thing is that we are around mid February. This year spring starts Saturday March 20. That is about 6 to 7 weeks from today. Continue reading “All Elements in Two Binary Search Trees”

Design HashMap – Third approach

Good day and hopefully you had a nice long weekend.

It seems that COVID-19 vaccines have been inoculated to about two million people in the USA. Apparently the vaccine is being well received by recipients. The issue at this point seems to be able to determine the efficacy against different virus mutations and how long our bodies will maintain resistance to it. In my humble opinion these two factors will take time to determine and must be backed up the actual (non edited) and unbiased data.

My sister sent me a link to the article “History isn’t just for patriots” by Daniel Immerwahr published by The Washington Post. I enjoy reading (mostly computer science related books, papers and articles) but also enjoy reading different subjects in order to understand the world which is inhabited by humans. In general we are extremely complex and hard to understand.

Reading the article I detected a taste of political bias. If you are interested I encourage you to read the article and form your own opinion.

At some point the author makes a comparison between history and geometry, in specific to the Pythagorean Theorem. I asked my wife when was the last time she recalls using it, if any, and for what purpose. She had no recollection of ever using it outside the geometry class while attending middle school. On the other hand, I use it often due that I design and develop software and have interest in algorithms and data structures among other computer science subjects.

On the other hand, we both have read several history books from different countries and at different times. To me unbiased history, which is very hard to find, provides facts that we can process and formulate an idea of what had happened in a certain part of the world during a specific period in time. With that information I hope to be able to better understand opinions from others. It is a fact that the winners write history.

Now a day we have a different type of influence. It comes in different forms and sources. For example I read the article in question that was published by The Washington Post and was sent to me by my sister who currently is living and teaching in China. After understanding the sources I need to read the article in an unbiased manner attempting to understand the set of points the author is providing and to understand the logic behind them. I have made my opinion and hopefully if you have a chance to read the article, you will also be able to generate your own educated opinion. Continue reading “Design HashMap – Third approach”

Validate Binary Search Tree

It is a gloomy day in the Twin Cities of Minneapolis and St. Paul. The good thing is that we have about two days until Thanksgiving Day 2020. This year we are cooking an 11 lbs. turkey. Typically my wife and I make an 18+ lbs. bird. Not only that but we are dropping half of it at our granddaughters place. On Thanksgiving Day we will be connecting with family via Jitsi and Skype. Continue reading “Validate Binary Search Tree”

Construct Binary Search Tree from Pre Order Traversal

It is Thanksgiving Week 2020 and we do not have a winner in the 2020 Presidential Elections yet. The amount of fraud in this year’s elections has been unprecedented. My comment has nothing to do with politics. It is just based on common sense for individuals 12 years of age and older. I have friends and relatives living in different parts of the world. Their confidence and respect in the USA is almost (never generalize) gone.

On multiple occasions and referring to different topics, I have mentioned in this blog a technique used when people want to understand the positions of each other. First both argue on behalf of their own positions. Then, and this is the key of the technique, they switch positions and argue in favor of the opposite position. It is amazing what you can learn about different ideas when you use this technique. The reason for this tends to be based on facts and logic. Continue reading “Construct Binary Search Tree from Pre Order Traversal”

Binary Search Tree to Greater Sum Tree – Java

Hello there. It is another Sunday morning during the COVID-19 pandemic. The current temperature in the Twin Cities of Minneapolis and St. Paul is about 30F and is sunny. As soon as I finish with this post my wife and I will stop by Target to get some sundries.

Yesterday my wife and I met my older son at Costco in Minneapolis. We get together every other weekend at Costco to do groceries. My wife and I got a 35 lbs. of beef chuck cut. Once we got home we cut smaller manageable portions, put them in bags and placed them in the freezer. We left one portion out. We cut it into smaller pieces, cut some potatoes, onions, garlic and carrots. Put them in a tray in a 550 degree oven for 10 minutes. The beef browned quite nicely. We then put the items in a pressure cook with some water and left them cooking for 1 ½ hours. We served them in on a thin base of very hot brown rice. I had two large servings. It was delicious. Continue reading “Binary Search Tree to Greater Sum Tree – Java”

Minimum Distance Between BST Nodes

Earlier today I read the article “Changing the clocks is a bad idea — and it should end, sleep experts say” by Jen Smith, CNN. The article makes a case for the USA to eliminate daylight savings time. It seems there is enough science behind the idea.

I am a morning person. I have a wake up alarm in my smart phone to wake up at 06:00 AM every day. Most of the time I get up about an hour early. Of course, in the evenings my wife and I are ready to hit the sack around 08:00 PM. At the start of summer the sun is up before 06:00 AM. At the start of winter, it is dark around 04:30 PM. Continue reading “Minimum Distance Between BST Nodes”

Lowest Common Ancestor in Binary Search Tree

It is a beautiful sunny summer day in the Twin Cities of Minneapolis and St. Paul. The high temperature for today in the city I live is forecasted to be 83 F. I prefer high temperatures in the range of 75 F to 80 F, but 83 F will have to do.

Yesterday I spent a few hours in front of my computers. My wife left early with a friend to go walking and shopping. My wife got back shortly after 11:00 AM. We made some potatoes with veggies in the grill using a cast iron pan. We always add some pepper, salt and a splash of oil with a high smoke point (i.e., avocado or peanut). Continue reading “Lowest Common Ancestor in Binary Search Tree”

Family Names

Yesterday my wife had an appointment at the hair salon. The gal that cut her hair commented that there were more people than usual complaining of seasonal allergies; some of them have never before experienced symptoms. My wife and I have some light allergies every season. Some days this year we have experienced strong symptoms. Hopefully things will get better soon.

Last evening in the local news, it was mentioned that due to the amount of water due to rain and melted snow, farmers are a couple weeks behind planting their crops. Having grains and vegetables is more important than experiencing allergy symptoms. Hopefully all will turn out well as the season progresses. The forecast for today calls for strong rain starting around mid morning and ending early tomorrow. Most of the rivers in this area are at or above normal flood levels. Hope the forecast falls short in moisture.

This week I had the opportunity to talk with a fellow software developer. We briefly discussed the approach of traversing a data structure using loops and recursion. It seems that if the number of objects is relatively small, recursion is elegant approach. That said, for large number of objects, recursion may fail due to execution stack limitations. Continue reading “Family Names”